C Program to print the majority element (> n / 2) in an array using Moore's Voting Algorithm

 

// Program by Akash Tripathi (@proakash256) 

 

// In this , we Loop through each element and

// maintains a count of majority element, and a majority index.

//If the next element is same then increment the count

// and if the next element is not same then decrement the count.

// If the count reaches 0 then changes the maj_index

// to the current element and set the count again to 1.

 

// Now again traverse through the array and

// find the count of majority element found.

// If the count is greater than half the size of the array,

// print the element.

#include <stdio.h>

int main()

{

    int n;

    printf("Enter the number of elements : ");

    scanf("%d", &n);

    int ar[n];

    printf("\nEnter the Elements :\n");

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

        scanf("%d", &ar[i]);

    // Algorithm Starts

    int count = 1 , index = 0;

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

    {

        if(ar[index] == ar[i])

            count = count + 1;

        else

            count = count - 1;

        if(count == 0)

        {

            count = 1;

            index = i;

        }

    }

    // ar[index] may or may not be the majority element

    // So , now we check -

    count = 0;

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

    {

        if(ar[index] == ar[i])

            count = count + 1;

    }

    if(count > (n / 2))

    {

        printf("\n%d is the Majority Element

                 occuring %d Times\n\n" , ar[index] , count);

    }

    else

    {

        printf("\nNo Majority Element found\n\n");

    }

    return 0;

}