# 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:

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