Description: A majority element is an element that occurs more than n/2 times in an array of size ‘n’. Given an array, find the majority element(if it exists).

Example:

Input:

2  6  8  2  7  2  2  2  9  8  2  2

Output:

2

In the above example, 2 is a majority element as it appears 7(>12/2) times.

Algorithm:

1. Initialize ‘majority’ as the first index (=0) of the array and ‘count’ as 0.
2. Scan the array from the 2nd element using the index ‘i’:

-If arr[i]==arr[majority] , count=count+1

Else,

count=count-1;

-If count==0,       majority=i   and     count=1;

3. Check if value at ‘majority’ index occurs more than n/2 times.

Implementation in C:

/* Function to print the majority element in a given array. If there is no majority element, "no majority element" is printed. */

void find_majority_element(int arr[], int n)

{

int majority = 0;

int count = 1;

int i;

for(i = 1; i < n; i++)

{

if(arr[majority] == arr[i])

count++;

else

count--;

if(count == 0)

{

majority = i;

count = 1;

}

}

/* now check to see if arr[majority] appears more than n/2 times. */

int occur=0;/* stores no of occurrences */

for(i=0;i<n;i++)

{

if(arr[i]==arr[majority])

occur++;

}

/* Now, check if value at ‘majority’ index occurs more than n/2 times.*/

if(occur>n/2)

printf("%d is Majority element",arr[majority]);

else

/*No majority element exists*/

printf("No majority element");

}

Time Complexity :

O(n)

Go to top