Question: An element is a majority if it appears more than n/2 times. Give an algorithm that takes an array of n elements and finds the majority element in that array. The array is not sorted.
Input: 8, 16, 8, 4, 8, 8, 8, 42, 16, 15, 8, 23, 4, 8, 15, 8, 8.
Output: Majority Element = 8
The most basic method of solving this problem is to take two loops and maintain a count of each of the element. If the count reaches more than (n/2) for any element, break the loop and return.
void printMajorityElement(int arr[], int size) { int count = 0; int i,j; int majority = 0; int found = 0; for(i = 0;i<size;i++) { count = 0; for(j = 0;j<size;j++) { if(arr[i] == arr[j]) count++; } if(count > (size/2)) { found = 1; majority = arr[i]; break; } } if(found) printf("Majority element = %d",majority); else printf("Majority element not present"); }
Time Complexity:- O(n2)
Space Complexity:- O(1)
Note: There can only be one majority element in an array.