Algorithms based on majority element

What is majority element in an array?
In an array of size n, if a specific element repeats itself more than half the times (> n/2 times), then it is called the majority element. If no such element exists, then the array is said to have no majority element in it.
Examples:
[3,2,2,3,3] -> 3 is the majority element
[4,4,5,7,3,3,3,4,4] -> 4 is the majority element
[1,2,3,4,5] -> no majority element at all.
[1,1,1,2,2,2] -> no majority element as the majority element has to repeat more than half the times (i.e. 4 times at least in this array)

How to check whether a number is majority element or not?
It is very simple and obvious. Given a number X and an array A, run through the array and make the count of X's in the array. If the count is more than A.size()/2, then X is the majority element.

Logic to find majority element?
Suppose X is the majority element of an array. If you find an element Y in the same array which is not equal to X, you can cancel one occurrence of Y and one occurrence of X from the array and still the resultant array will have X as the majority element. This cancellation will reduce the size of both the parts of the array, i.e. the part (may not be contiguous) having majority element, and the one having rest of the elements.
Example: [3,1,2,3,3] -> In this array, 3 is the majority element. If you are able to find one non-majority element (say 1), you can cancel one occurrence of both 1 and 3 and still 3 will be the majority element. i.e. [2,3,3] obtained after cancelling one 3 and one 1 also has 3 as the majority element.

Similarly, take 2 elements which are not majority elements, say Y and Z. If you cancel both of them, the majority element will still be the same. i.e. in the above example, if you cancel two non majority elements 1 and 2, the resultant array will have [3,3,3] in which 3 is majority element once again.

In other words, you can pick any 2 elements from the array, and you can discard them if both of them are not the majority elements.


Solution:
Given an array A[0..n-1], your assignment is to find the majority element in it.
Let counter be the variable which records the number of occurrences of the majority element. Initially it will be 0.
Whenever the counter is less than or equal to zero, take the next element in A as majority element. Increment the counter when you see the same element and decrement it when you see a different element. Do it again if the counter becomes zero once again.

counter = 0
majority_index = -1
// Find majority element
for i in 0..Arr.size()-1
  if counter == 0
    majority_index = i
  end
  counter += Arr[i] == Arr[majority_index]
end


// Check the correctness
majority_count = 0
for j in 0..Arr.size()-1
  if Arr[j] == Arr[majority_index]
    majority_count ++
  end
end
if (majority_count > Arr.size()/2)
  return Arr[majority_index]
else
  throw "No majority element found"
end

E.g. 1,2,4,2,5,6,3,4,4,2,4,4,4,4,4
counter = 0
Start with 1 as majority element.
Next element is 2 which is not 1. So discard both.
Now 4 becomes the majority element and counter will be 1
when 2 comes again, counter will become 0, and so till now no majority element exists.
Next 5 and 6 gets discarded similarly as both are different.
Similarly, 3 and 4 will get discarded, and again 2 and 4 will get discarded.
Now the only array having majority element is [4,4,4,4,4] and the counter keeps incrementing to 5.
Now check whether 4 is the real majority element in the array. If so, you can return 4.

Problem 2 "Find element which occurs at least half the times"
Good that you now know how to find the majority element. Now, given that you need to find the element which occurs at least half the times in the array, how will you proceed? Remember, this is a different problem. As per the majority element, it should occur more than half the times, but now the problem has been modified to find that element which repeats at least half the times.
Solution:
We can use the majority algorithm that we discussed above in all the cases except when the element that needs to be found occurs exactly half the times in the array. We can change the solution a bit to catch that case also. In the array, check whether the first element is the majority element; if so, return it. Else, discard the first element in the array. Now after discarding, we can apply the above described normal majority element algorithm itself as now the majority element is guaranteed to be more than half the number of times in the array.