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;
 }

Answer 3

Algorithm that you have explained works on the following idea:

1. If two successive elements are equal, then that is the potential majority element and include it in the result set (for further processing)

2. If two elements are distinct, then this particular pair does not decide the winner.

Point #2 is crucial - suppose that (A1, A2) pair contains the majority element (A1) and another minority element (A2). Remove this pair. A1 remains majority in the remainder of the array.

If you have understood this explanation, then you understand why nothing is added to B when elements differ.

Corrolary to the algorithm, regarding an array containing odd number of elements, would then be: add an odd element to B. Reason is the same as #1: it might be the majority element, and it should be included in the output just to be sure that its count is not lost in the process.

Anyway, the whole thing can be done without the other array B. Here you can find much simpler algorithm: Finding a Majority Element in an Array

Answer 4

Here are three algorithms that solve the problem:

1) Scan the elements of the array, accumulating a frequency of each distinct element using some sort of dictionary (hash table, balanced tree). When the scan is complete, pick the only dictionary item with a count greater than n/2, or report that no element has a majority.

2) The majority element must be the median of the array if it exists. Compute the median using the median-of-five technique or any other algorithm, and confirm that it is greater than n/2.

3) An algorithm of Boyer and Moore (the same guys that did the string-matching algorithm) picks the first array element as the candidate item and assigns a count of 1, then scans the array, adding 1 to the count if the next item is the same as the current candidate, subtracts 1 from the count if the next item differs from the current candidate, and resets the candidate to the next array element, with a count of 1, whenever the count reaches 0. At the end of the scan the current candidate is a member of the majority if a majority exists, so a second scan is required to confirm that the candidate does form a majority.

I discuss and implement all three algorithms at my blog.

Answer 5

I think your algorithm won't work when N is even too. I can prove it with an example:

Consider array of 8 elements say 2,2,1,1,3,2,2,2. Now your B array will be 2,1,2 as per you statement. If you repeat the above step again. There won't be any candidates. But the actual answer here is '2'. So this method is definitely wrong.

This problem was discussed on Geeks for geeks. I think this will help you:

http://www.geeksforgeeks.org/majority-element/