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).
Write a function which takes an array and emits the majority element (if it exists), otherwise prints NONE as follows:
I/P : 3 3 4 2 4 4 2 4 4
O/P : 4
I/P : 3 3 4 2 4 4 2 4
O/P : NONE
A simple solution would be running 2 loops and check for all elements and store count of all elements… Time complexity will be O(n^2).
Can you think of a better solution …
here I’m giving You a better solution .. Time complexity – O(n)
Using Moore’s Voting Algorithm)
This is a two step process.
1. Get an element occurring most of the time in the array. This phase will make sure that if there is a majority element then it will return that only.
2. Check if the element obtained from above step is majority element.
1. 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.
<br />#include <bits/stdc++.h>
using namespace std;
int find_priority(int arr[], int n){
int c = 1,index = 0;
for(int i = 1; i < n; i++){
if(arr[index] == arr[i]){
c++;
}
else{
c--;
}
if(c == 0){
index = i;
c = 1;
}
}
return arr[index];
}
int main(){
int n;
cout<<"enter value of n"<<endl;
cin>>n;
int arr[n];
cout<<"enter array"<<endl;
for(int i = 0; i < n; i++){
cin>>arr[i];
}
int pr_ele = find_priority(arr,n);
int c = 0;
for(int i = 0; i < n; i++){
if(arr[i] == pr_ele)
c++;
}
if(c > n/2){
cout<<"majority element found"<<endl<<"element is "<<pr_ele<<endl<<"count is "<<c;
}
else cout<<"no majority element present";
}
Output :-
Myprogworld 