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

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:

- One loop for picking an element
- 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:**

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

**Space Complexity **= O(1)

where,

n -> size of the array

## Leave a Reply