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 :-
You must be logged in to post a comment.