Majority Element

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).

Idea : To find the majority element using 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

#include<iostream> using namespace std; int main(){ int arr[] = {2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 2, 4, 4}; //{1, 2, 4, 4, 10, -8}; int n = sizeof(arr)/sizeof(arr[0]); int count, majorityElt; majorityElt = arr[0]; count = 1; for(int i = 1 ; i < n ; i++ ){ if(arr[i] == majorityElt){ count++; } else { count--; } if(count == 0){ count = 1; majorityElt = arr[i]; } } count = 0; for(int i = 0 ; i < n ; i++){ if(arr[i] == majorityElt){ count++; } } if(count > n/2){ cout << majorityElt << " is the majority element " << endl; } else{ cout << "No such element exists" << endl; } return 0; }