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

 
If video does not load, Click here
 
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