How to check for Majority Element in an array in C++

By Akash Dileep

In this tutorial, we are going to see some ways to find the majority element in an array in C++.

A majority element in an array is that element whose frequency is greater than ‘n/2’, where ‘n’ is the size of the array.

Example:

Input -> {3,3,2,1,3,3}
Output -> 3
//Because the frequency of 3 is more than n/2

Input -> {1,3,2,3,5,4}
Output -> No Output
//Because no element has frequency more than n/2

 

C++ program to check Majority Element in an array

BRUTE FORCE

In the brute force technique, we check the frequency of each element and print that element whose frequency is greater than n/2 if present.

For this, we require two loops:

  1. One loop for picking an element
  2. And a nested loop for counting the frequency

Let’s see the implementation.

Below is our C++ code that can find and check for majority element in an array:

#include<bits/stdc++.h>
using namespace std;

/*function that checks for majority element,
returns true and prints the majority element if present
else returns false*/
bool check(vector<int> a, int n)
{

    //fist loop for picking the element
    for (int i=0;i<n;i++)
    {

        //for storing count of the element
        int freq=0;

        //nested loop for counting frequency
        for (int j=i;j<n;j++)
        {
            if (a[i]==a[j])
                freq++;
        }

        /*after each time the nested loop is finished we
        have to check weather we got the majority element or not*/
        if (freq>(n/2))
        {
            cout<<"Majority element: "<<a[i];
            return true;
        }
    }
    return false;
}
int main()
{
    int n;
    cout<<"Enter the size the array: ";
    cin>>n;
    vector<int> a(n);
    cout<<"Enter the elements of the array: ";
    for (int i=0;i<n;i++)
        cin>>a[i];

    //this coondition is executed when there is no majority element
    if (!check(a, n))
        cout<<"No majority element is present";
    return 0;
}

Input/Output 1:

Enter the size the array: 6
Enter the elements of the array: 3 3 2 1 3 3
Majority element: 3

Input/Output 2:

Enter the size the array: 6
Enter the elements of the array: 1 3 2 3 5 4
No majority element is present

Time Complexity = O(n*n)

Space Complexity = O(1)

where,
n -> size of the array

 

USING SORTING

In this technique, we will sort the array and then pick the middle element and then check if its frequency is greater than n/2 or not. The reason for picking the middle element is because if an array has a majority element then it will definitely acquire the middle position after the array is sorted as the frequency if more than n/2.

Let’s see the implementation.

Code:

#include<bits/stdc++.h>
using namespace std;

/*function that checks for majority element,
returns true and prints the majority element if present
else returns false*/
bool check(vector<int> a, int n)
{
    //function sorts the array
    sort(a.begin(), a.end());

    //storing the mid index
    int mid=n/2;

    //variables for storing frequency
    int freq=0;

    /*in this loop we are calculating
    the frequency of the mid element*/
    /*this loop is used for comfirming that the
    middle element is indeed the majority element*/
    for (int i=0;i<n;i++)
    {
        if (a[mid]==a[i])
            freq++;
    }

    //executes if frequency is greater than n/2
    if (freq>(n/2))
    {
        cout<<"Majority element: "<<a[mid];
        return true;
    }
    return false;
}

int main()
{
    int n;
    cout<<"Enter the size the array: ";
    cin>>n;
    vector<int> a(n);
    cout<<"Enter the elements of the array: ";
    for (int i=0;i<n;i++)
        cin>>a[i];

    //executes when there is no majority element
    if (!check(a, n))
        cout<<"No majority element is present";
    return 0;
}

Input/Output 1:

Enter the size the array: 6
Enter the elements of the array: 3 3 2 1 3 3
Majority element: 3

Input/Output 2:

Enter the size the array: 6
Enter the elements of the array: 1 3 2 3 5 4
No majority element is present

Time Complexity = O(n) + O(nlogn) = O(nlogn)

Space Complexity = O(1)

where,
n -> size of the array

 

USING HASHMAP

In this technique, we will store the element along with its count in an unordered map after that we will fetch the element with maximum frequency from the unordered map and check whether its frequency is greater than n/2 or not.

Let’s see the implementation.

Code:

#include<bits/stdc++.h>
using namespace std;

/*function that checks for majority element,
returns true and prints the majority element if present
else returns false*/
bool check(vector<int> a, int n)
{

    //unordered_map for storing element along with its count
    /*elements will be stored in key-value pair where,
    key will be elements(first) and value will be its
    count(second)*/
    unordered_map<int, int> mp;

    //elements along with their count are stored in unordered_map
    for (int i=0;i<n;i++)
        mp[a[i]]++;

    int element, freq=0;

    /*initializing an iterator that will be used while
    iterating through unordered_map*/
    unordered_map<int, int>::iterator i;

    /*this loop is used for finding the element
    with max frequency in the unordered_map*/
    for (i=mp.begin();i!=mp.end();i++)
    {
        if ((i->second)>freq)
        {
            freq=i->second;
            element=i->first;
        }
    }

    /*checking weather the frequency of maximum
    the occurring number is greater than n/2*/
    if (freq>(n/2))
    {
        cout<<"Majority element: "<<element;
        return true;
    }
    return false;
}

int main()
{
    int n;
    cout<<"Enter the size the array: ";
    cin>>n;
    vector<int> a(n);
    cout<<"Enter the elements of the array: ";
    for (int i=0;i<n;i++)
        cin>>a[i];

    //executes when there is no majority element
    if (!check(a, n))
        cout<<"No majority element is present";
    return 0;
}

Input/Output 1:

Enter the size the array: 6
Enter the elements of the array: 3 3 2 1 3 3
Majority element: 3

Input/Output 2:

Enter the size the array: 6
Enter the elements of the array: 1 3 2 3 5 4
No majority element is present

Time Complexity = O(n)

Space Complexity = O(n)

where,
n -> size of the array

 

(MOST OPTIMIZED) USING MOORE’S VOTING ALGORITHM

In this technique, we will first find the candidate (the element with maximum frequency) and then calculate its frequency and check whether its frequency is greater than n/2 or not.

Let’s see the implementation.

Code:

#include<bits/stdc++.h>
using namespace std;

//function returns the element with maximum frequency
int candidate(vector<int> a, int n)
{
    /*major will hold the index of the candidate,
    initially, it will hold the index of the first element*/
    int major=0, freq=1;

    //finding the element with maximum frequency
    for (int i=1;i<n;i++)
    {
        if (a[major]==a[i])
            freq++;
        else
            freq--;

        /*whenever freq (frequency) becomes
        zero major is assigned a new element*/
        if (freq==0)
        {
            major=i;
            freq=1;
        }
    }
    return a[major];
}

/*function that checks for majority element,
returns true and prints the majority element if present
else returns false*/
bool check(vector<int> a, int n)
{

    //getting the candidate
    int element=candidate(a, n);
    int freq=0;

    //calculating the frequency of candidate
    for (int i=0;i<n;i++)
    {
        if (element==a[i])
            freq++;
    }

    /*checking weather the frequency
    candidate is greatewr than n/2*/
    if (freq>(n/2))
    {
        cout<<"Majority element: "<<element;
        return true;
    }
    return false;
}

int main()
{
    int n;
    cout<<"Enter the size the array: ";
    cin>>n;
    vector<int> a(n);
    cout<<"Enter the elements of the array: ";
    for (int i=0;i<n;i++)
        cin>>a[i];

    //executes when there is no majority element
    if (!check(a, n))
        cout<<"No majority element is present";
    return 0;
}

Input/Output 1:

Enter the size the array: 6
Enter the elements of the array: 3 3 2 1 3 3
Majority element: 3

Input/Output 2:

Enter the size the array: 6
Enter the elements of the array: 1 3 2 3 5 4
No majority element is present

Time Complexity = O(n) + O(n) = O(n)

Space Complexity = O(1)

where,
n -> size of the array

Leave a Reply

Your email address will not be published. Required fields are marked *