A majority element, is an element that is repeated more than half of the times.
Example:
[1, 2, 3, 4, 4, 4, 4, 4, 5]
Output: 4.
Total number of elements are 9, and 4 is repeated 5 times. It has repeated more than half of the times.
We can solve this problem by using Moore Voting Algorithm. This algorithm will work if there is a majority element. If there is no majority element you will get a wrong result.
Below is how the algorithm works:
1. Consider first element as a majority_element, and use a count variable to increment every time we encounter that variable.
2. Decrement the counter, if the variable at the current index is different than the majority_element.
3. If the counter hits 0, consider the current element as majority element and continue through the array.
4. At the end, the number saved in “majority_element” is the result.
5. This will work on unsorted array also.
In the solution, I have given debug statements, so that you can understand the exact flow.
Solution in C++
#include<iostream>
#include<vector>
#include<string.h>
using namespace std;
int majority_element_moore_voting_algorithm(vector<int> &num)
{
int major=num[0];
int count = 1;
cout<<"============start debugging============"<<endl;
cout<<"Step 1: majority element = "<<major<<" count = "<<count<<endl;
for(int i=1; i<num.size();i++)
{
cout<<"Step 2: majority element = "<<major<<" count = "<<count<<" num = "<<num[i]<<endl;
if(count==0)
{
count++;
major=num[i];
cout<<"Step 3: majority element = "<<major<<" count = "<<count<<" num = "<<num[i]<<endl;
}
else if(major==num[i])
{
count++;
cout<<"Step 4: majority element = "<<major<<" count = "<<count<<" num = "<<num[i]<<endl;
}
else
{
count--;
cout<<"Step 5: majority element = "<<major<<" count = "<<count<<" num = "<<num[i]<<endl;
}
}
cout<<"============end debugging============"<<endl;
return major;
}
int main()
{
vector<int> number = {1, 2, 3, 4, 5, 5, 5, 5, 5, 5, 6};
int majority_element = majority_element_moore_voting_algorithm(number);
cout<<"The majority element is "<<majority_element<<endl;
return 0;
}
Output:
============start debugging============
Step 1: majority element = 1 count = 1
Step 2: majority element = 1 count = 1 num = 2
Step 5: majority element = 1 count = 0 num = 2
Step 2: majority element = 1 count = 0 num = 3
Step 3: majority element = 3 count = 1 num = 3
Step 2: majority element = 3 count = 1 num = 4
Step 5: majority element = 3 count = 0 num = 4
Step 2: majority element = 3 count = 0 num = 5
Step 3: majority element = 5 count = 1 num = 5
Step 2: majority element = 5 count = 1 num = 5
Step 4: majority element = 5 count = 2 num = 5
Step 2: majority element = 5 count = 2 num = 5
Step 4: majority element = 5 count = 3 num = 5
Step 2: majority element = 5 count = 3 num = 5
Step 4: majority element = 5 count = 4 num = 5
Step 2: majority element = 5 count = 4 num = 5
Step 4: majority element = 5 count = 5 num = 5
Step 2: majority element = 5 count = 5 num = 5
Step 4: majority element = 5 count = 6 num = 5
Step 2: majority element = 5 count = 6 num = 6
Step 5: majority element = 5 count = 5 num = 6
============end debugging============
The majority element is 5