PROGRAMMING INTERVIEWS

Example:
Input : 3 3 4 2 4 4 2 4 4
Output : 4

Input : 3 3 4 2 4 4 2 4
Output : NONE

Solution 1: A basic solution is to scan entire array for checking for every element in the array. If any element occurs more than n/2 time, prints it and break the loop. This will be of O(n^2) complexity.

Solution 2: Sort the entire array in O(nlogn) and then in one pass keep counting the elements. This will be of O(nlogn) + O(n) = O(nlogn) complexity.

If we are sure that there is a majority element for sure than we can do it in constant time in sorted array. I am leaving an exercise to readers that how can we do that in constant time.

A better solution: From definition, an element is a majority element if it occurs more than n/2 times in the array. Lets assume that there is a majority element ‘x’ in the array. Now if we cancel different elements with each other than at the end we will be left with ‘x’. Think why this is true before moving forward. (Coz element x is there for more than n/2 times so at the most n/2 elements will be cancelled.)

Example: 3 3 6 2 6 6 2 6 6
In above array, 3, 3, 2 and 2 will cancel only four 6’s. One 6 will stay as candidate for majority element.

How to cancel numbers: We will have a count variable initialized to zero and a variable which will hold x (running candidate for majority element). We will increment count if we find an element same as x and decrement count if we find an element different from x. When count becomes zero, we put current element in x and make count as 1.

For above example, steps will be as follows:

Clearly, there will always be an element in x at the end. But that is not surely a majority element. For example in array “3 3 6 6 6 2 2 1 1”, we will have x=1 in the end. But that will only be true when there is no majority element. So after traversing complete array and finding x, we should check for it’s count in original array. If count is greater than n/2, x is our answer else there is no majority element.

Code:

bool majority(int arr[], int n)
{
  int x, cnt, i;
  x = INT_MIN;
  cnt = 0;
  for (i=0; i<n; i++)
  {
      if (cnt == 0)
      {
          x = arr[i];
          cnt++;
      }
      else if(arr[i] == x)
          cnt++;
      else
          cnt--;
  }
  //checking x's count in arr[]
  cnt = 0;  
  for (i=0; i<n; i++)
  {
      if(x == arr[i])
          cnt++;
  }

  if (cnt > n/2)
      cout << "majority element = " << x<< endl;
  else
      cout << "no majority element" << endl;
}

Complexity: Since we are traversing the array just twice, once for finding x and 2nd time for finding count. Time complexity is O(n) + O(n) = O(n).