CODEWITHSUNDEEP
arraysalgorithmperformancesortingdivide-and-conquer
gaurav tripathi
gaurav tripathi

Reputation: 27

Rare elements in arrays

We are given a sorted array A[1..n] of n integers. We say an element x E A is rare if it occurs in A strictly less than n/10 times. That is, x is rare if there is some index 1 <= i <= n such that A(i) = x, and there are strictly less than n/10 distinct indices j for which A(j) = x. Our goal is to find a rare element, or output that A contains no rare elements.

Input: A sorted array A[1..n] of n integers.

Output: A rare element x E A, or the output “No rare element exists in A.”

Is there an O(log n) time algorithm for the rare element problem? What is it?

T(n) = 10 T(n/10) + O(1) gives O(n) time which is not good enough for me.

Upvotes: 1

Views: 362

Answers (1)

Gerald Agapov
Gerald Agapov

Reputation: 220

Yes, it's possible to do it in O(log n). I assume, that you already have this array in memory. Otherwise it's impossible to do it faster than in O(n), because you need to read array at least.

Let's say that step is the biggest integer that is less than n/10. If step is equal to zero then we don't have rare elements obviously.

Consider the following algorithm:

int start = 1;
while (true) {
  if (n - start + 1 <= step) {
    OutputRare(A[start]); Exit;
  }
  int next_index = start + step;
  if (A[start] != A[next_index]) {
    OutputRare(A[start); Exit;
  }
  // Here we need to find the smallest index starting from start with
  // element that is not equal to A[start]. If such element does not
  // exist function returns -1.
  next_index = FindFirstNonEqual(A[start], start);
  if (next_index == -1) {
    // There is no rare elements
    Exit;
  }
  start = next_index;
}

This algorithm either returns rare element, or increases start by at least step. Which means that it will increase start ~10 times (because every step is about n/10). FindFirstNonEqual can be implemented using binary search, which means that total complexity is O(10log n) = O(log n).

Upvotes: 2

Related Questions