### Moore’s Voting Algorithm

In this post , we will learn how to find the majority element in the array.

There are number of ways with which we can find the majority element in an array.

**A majority element is a element which appears more than n/2 times in the array.**

### Solution 1:

The first solution is to run a outer loop (i.e loop i) and then the inner loop (i.e loop j) and make a count variable to keep track of element having maximum count.

And then print the element which has count greater than n/2.

The cons of this approach is that it takes time complexity of O(n*n), which is not recommended as a optimized code.

**Solution 2:- Using Moore Voting Algorithm**

**Time complexity :- **O(n)

Steps:- 1: First find the majority element by running the outer loop with the two candidates (variables first and second) use and maintain their counts. There may be a chance that we have more than one majority element(greater than n/2) present in the array. 2:- Now make the two count again zero. 3:- Now iterate again through the array to find the one element which is occurring maximum times.

### Code to find the majority element in the array:-

#include<bits/stdc++.h> using namespace std; int majority(int arr[],int n) { int ifirst=INT_MAX,isecond=INT_MAX; int icount1=0,icount2=0; for(int i=0;i<n;i++) { if(ifirst==arr[i]) icount1++; else if(isecond==arr[i]) icount2++; else if(icount1==0) ifirst=arr[i]; else if(icount2==0) isecond=arr[i]; else { icount1--; icount2--; } } icount1=0; icount2=0; for(int i=0;i<n;i++) { if(ifirst==arr[i]) icount1++; else if(isecond==arr[i]) icount2++; } if(icount1>n/2) return ifirst; if(icount2>n/2) return isecond; return -1; } int main() { int arr[] = { 4 ,3 ,3 ,1 ,5 ,5 ,9 ,5 ,5 ,0 ,5}; int n = sizeof(arr) / sizeof(arr[0]); cout << majority(arr, n) << endl; return 0; }

CommentsNo comment yet.