C/C++ Program for Majority Element

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