Finding Majority element in an array

Question

I want to discuss an algorithm here which I found in a data structure book. This book presents a sketch of the algorithm to find the majority element (appears more than N/2 ) in an array of size N . The sketch of the algorithm is as follows:

First, a candidate majority element is found ( this is the harder part ). This candidate is the only element that could possibly be the majority element.The second step determines if this candidate is actually the majority. This is just a sequential search through the array. To find a candidate in the array, A, form a second array B. Then compare A1,A2. If they are equal, add one of these to B; otherwise do nothing. Then compare A3 and A4. Again if they are equal, add one of these to B; otherwise do nothing. Continue in this fashion until the entire array is read. Then recursively find a candidate for B; this is the candidate for A.

I figured out if the N is even, algorithm works fine. But what if N is odd ? How we can handle this case?

Answer 1

Majority Element:

A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).

Finding a Candidate:

The algorithm for first phase that works in O(n) is known as Moore’s Voting Algorithm. Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end if it is a majority element.

findCandidate(a[], size)
1.  Initialize index and count of majority element
     maj_index = 0, count = 1
2.  Loop for i = 1 to size – 1
    (a)If a[maj_index] == a[i]
        count++
    (b)Else
        count--;
    (c)If count == 0
        maj_index = i;
        count = 1
3.  Return a[maj_index]

Above algorithm loops through each element and maintains a count of a[maj_index], If next element is same then increments the count, if next element is not same then decrements the count, and if the count reaches 0 then changes the maj_index to the current element and sets count to 1. First Phase algorithm gives us a candidate element. In second phase we need to check if the candidate is really a majority element.

Second phase is simple and can be easily done in O(n). We just need to check if count of the candidate element is greater than n/2.

Answer 2

A majority element in an array A[] of size n is an element that appears more than n/2 times

 int find(int[] arr, int size) { 
  int count = 0, i, mElement;
 for (i = 0; i < size; i++) {
    if (count == 0)
        mElement = arr[i];
    if (arr[i] == mElement) 
        count++;
    else
        count--;
  }
 count = 0;
 for (i = 0; i < size; i++)
    if (arr[i] == mElement)
         count++;
  if (count > size/2)
        return mElement;
  return -1;
 }