Moore’s Voting Algorithm
Basic idea of the algorithm is that if each occurrence of an element e can be cancelled with all the other elements that are different from e then e will exist till end if it is a majority element.
Approach: This is a two-step process.
The first step gives the element that may be the majority element in the array. If there is a majority element in an array, then this step will definitely return majority element, otherwise, it will return candidate for majority element.
Check if the element obtained from the above step is majority element. This step is necessary as there might be no majority element.
Algorithm:
Loop through each element and maintains a count of majority element, and a majority index, maj_index.
If the next element is same then increment the count if the next element is not same then decrement the count.
if the count reaches 0 then change the maj_index to the current element and set the count again to 1.
Now again traverse through the array and find the count of majority element found.
If the count is greater than half the size of the array, print the element
Else print that there is no majority element.
Last updated