*822*

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(n^{2})

*Space Complexity:-* O(1)

Note: There can only be one majority element in an array.

**Method 2:- Using sorting**

**Method 3:- Using a single scan**