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:
- Consider first element as a majority_element, and use a count variable to increment every time we encounter that variable.
- Decrement the counter, if the variable at the current index is different than the majority_element.
- If the counter hits 0, consider the current element as majority element and continue through the array.
- At the end, the number saved in “majority_element” is the result.
- 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