C Program to Find Majority Element of Array

  • Write a program to find the majority element of an array.
  • C program to find majority element using Moore’s Voting Algorithm.

Given an integer array of size N. We have to find the majority element of given array.
In an array of size N, a majority element appears more than N/2 times.
For Example :
Input Array : 4 2 8 7 2 1 2 2 2
Majority Element is 2

Method 1 : Brute Force
Let inputArray be an integer array of size N.
  • Count of frequency of each element of array using two for loop.
  • Outer for loop will fix one element(let's say K) and inner for loop will count the occurrences of K in inputArray.
  • If count of K is more than N/2 then K is a majority element.
  • If we don't find any element whose count is > N/2 then inputArray doesn't contain any majority element.
Time Complexity : O(n2)
Method 2 : By Sorting input array
Let inputArray be an integer array of size N.
  • Sort inputArray using any nLogn average time sorting algorithm like quick sort, merge sort etc.
  • After sorting all identical elements will group together in adjacent locations.
  • Traverse inputArray and find the count of identical adjacent element.
  • If we found any element whose count is more than N/2 then same is a majority element.
Time Complexity : O(nLogn)
Method 3 : Using Moore’s Voting Algorithm
Let inputArray be an integer array of size N. This approach is a two step method as follows:
  • Using Moore's voting algorithm, find a potential candidate for majority element. This step returns a element occurring maximum number of times in array(let this element be K).
  • Second step is to verify whether K is actually majority element or not. We will traverse inputArray and count the frequency of K. If it is more than N/2 then it is majority element else no majority element exists in inputArray.
Moore’s Voting Algorithm: We will cancel out each occurrence of K for all other element other than K. If count of K is non zero till end of array then K is a majority element.
  • Assume first element of array is majority element and initialize the count of majority element to 1. Traverse inputArray from index 0 to N-1.
  • If current element is equal to majority element then increment count else decrement count.
  • If count is equal to zero then set current element as majority element and count as 1.
Time Complexity : O(n)

C program to find majority element of array

#include <stdio.h>
#define ARRAY_SIZE 100

void getMajorityElement(int *array, int size) {
 int i, majorityIndex = 0, count = 1;
    /* Find Majority Element */
    for(i = 1; i < size; i++) {
     /* Check if current element is same as majority element, 
  If yes then increment count otherwise decrement count */
        if(array[majorityIndex] == array[i])
            count++;
        else
            count--;
        
        if(count == 0) {
            majorityIndex = i;
            count = 1;
        }
    }
    /* Verify, If array[majorityIndex] is the majority element */
    count = 0;
    /* Count the frequency of array[majorityIndex] in array */
    for (i = 0; i < size; i++) {
        if(array[i] == array[majorityIndex])
            count++; 
 }
 /* Check if count of majority element is more than size/2, 
 If yes, then it is a majority element otherwise not  */
    if(count > (size/2))
        printf("Majority Element : %d\n", array[majorityIndex]);
    else
        printf("No Majority Element Found\n");
}

int main(){
    int i, array[ARRAY_SIZE], count, sum;
    printf("Enter the number of elements in Array\n");
    scanf("%d", &count);
    
    printf("Enter %d numbers\n", count);
    for(i = 0; i < count; i++){
 scanf("%d", &array[i]);
    } 
 
    getMajorityElement(array, count);

    return 0;
}
Output
Enter the number of elements in Array
9
Enter 9 numbers
4 2 8 7 2 1 2 2 2
Majority Element : 2

Enter the number of elements in Array
9
Enter 9 numbers
4 2 8 7 2 1 2 1 3
No Majority Element Found
Posted by
Labels: ,