Home » Interview coding problems/challenges

C/C++ Program for Majority Element

C/C++ implementation to find majority elements using multiple approaches.
Submitted by Shivang Yadav, on April 25, 2022

Majority Element

An element ele of an array of size N, whose frequency of occurrence is more than N/2 i.e. the element that appears more than N/2 times in the array is known as the Majority Element.

This element occurs the maximum number of times and there is only one majority element in an array.

Example:

arr[] = {1, 5, 1, 2, 1, 1, 3, 1, 2, 1}
Majority element = 1
N = 10, occurrence frequency = 6

In this article, we will be creating a function in C/C++ to find the majority element of the array. The input to the function is an array arr[] and its size N.

The function will print the majority element if it exists otherwise print "No majority element exists".

Input:
arr[] = {1, 5, 1, 2, 1, 1, 3, 1, 2, 1}
N = 10

Output:
1

Solution Approach:

One method to find the majority element of an array is by using nested loops. The outer loop is used to loop over the elements of the array. And for each element of the array, we will count the number of equal valued elements using another array. And update the max frequency element. After the end of the loop, we will check if the frequency is greater than N/2. If yes, print the maximum frequency element otherwise print "No majority element exists".

Program to find the Majority Element of array

#include <iostream>
using namespace std;

void findMajorityElement(int arr[], int n){
    int maxOccCount = 0;
    int maxOccVal = -1;
    
    for (int i = 0; i < n; i++) {
        int occCount = 0;
        for (int j = 0; j < n; j++) {
            if (arr[i] == arr[j])
                occCount++;
        }
        if (occCount > maxOccCount) {
            maxOccCount = occCount;
            maxOccVal = i;
        }
    }
    
    if (maxOccCount > n / 2)
        cout << arr[maxOccVal] << endl;
    else
        cout << "No Majority Element" << endl;
}

int main(){
    int arr[] = { 1, 5, 1, 2, 1, 1, 3, 1, 2, 1 };
    
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "The Elements of array are \n";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    cout << "\nMajority Element of the array is ";
    findMajorityElement(arr, n);
    
    return 0;
}

Output:

The Elements of array are
1 5 1 2 1 1 3 1 2 1 
Majority Element of the array is 1

Approach 2:

Another method is Moore's Voting Algorithm also known as Boyer-Moore Majority Voting Algorithm is an algorithm to find the majority element of an array.

The idea is to loop over the array finding elements which has greatest occurrence frequency and then check if it is a majority number or not.

Algorithm :

• Loop through the elements of the array
  • Fix a maxFreq element and its occurrence frequency based on the next element.
    • Decrease frequency, if next element is different
    • Increase frequency, if next element is same
  • If the occurrence count is 0, fix the next element as a major element.
• After the loop ends, check if the maxFreq element found is a major element.
  • If it is a major element, return it.
  • If it is not major element print no major element

Program to find majority element using Moore's Voting algorithm

#include <iostream>
using namespace std;

int findMaxFreqElement(int arr[], int size){
    int maxFreqInd = 0, maxFreq = 1;
    
    for (int i = 1; i < size; i++) {
        if (arr[maxFreqInd] == arr[i]) {
            maxFreq++;
        }
        else {
            maxFreq--;
        }
        if (maxFreq == 0) {
            maxFreqInd = i;
            maxFreq = 1;
        }
    }
    return arr[maxFreqInd];
}

void findMajorityElement(int arr[], int size){
    int maxFreq = findMaxFreqElement(arr, size);
    int freq = 0;
    
    for (int i = 0; i < size; i++)
        if (arr[i] == maxFreq)
            freq++;
    if (freq > size / 2)
        cout << "\nMajority element is " << maxFreq << " ";
    else
        cout << "No Majority Element";
}

int main(){
    int arr[] = { 1, 5, 1, 2, 1, 1, 3, 1, 2, 1 };
    
    int size = (sizeof(arr)) / sizeof(arr[0]);
    
    cout << "The Elements of array are \n";
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }

    findMajorityElement(arr, size);

    return 0;
}

Output:

The Elements of array are 
1 5 1 2 1 1 3 1 2 1 
Majority element is 1