Home Â» Technical Interview Questions Â» Array Interview Questions Â» Majority Element

# Majority Element

Given a sorted array, we need to find the majority element from the sorted array. Majority element: Number occurring more than half the size of the array. Here we have given a number x we have to check it is the majority_element or not.

## Example

Input

5 2

1 2 2 2 4

Output

2 is a majority element

## Approach 1 for finding Majority Element

We use the concept of Binary Search but in a tricky manner. The binary search can be modified easily to check the first occurrence of the given number x.

### Algorithm

1. Check if the middle element of array is x or not .Because any majority_element must be at middle of array if it occurs more than N/2 times.
2. If present then do a custom Binary Search to find the first occurrence of x.
3. The index obtained is say k,then check ifÂ  (k+N/2)thÂ  index also has x. If yes then x is a majority_element.

NOTE: Use lower_bound and higher_bound STL functions to do the task easily.

### C++ Program for finding Majority Element

```#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,x;
cin>>n>>x;
int arr[n];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
int low=lower_bound(arr,arr+N,x)-arr; //index of first occurence of the element
int high=upper_bound(arr,arr+N,x)-arr; //index of the last occurenece of element
if(high-low>N/2)
cout<<x <<" is a majority element\n";
else
cout<<x <<" is not a majority element\n";
return 0;
}```
```5 2
1 2 2 2 4```
`2 is a majority element`

## Approach 2 for finding Majority Element

### Algorithm

Loop till the half of the array doing :
a. If the present element is x then check if (the present index + N/2)th index contains x.
b. If it does then x is a majority_element.
c. Else x is not a majority_element.

### C++ ProgramÂ  for finding Majority Element

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int N,x;
cin>>N>>x;
int arr[N];
for(int i=0;i<N;i++)
{
cin>>arr[i];
}
int end;
if(N%2)
end = N/2+1;
else
end = N/2;

for(int i=0;i<end;i++)
{
if(arr[i] ==x and x == arr[i+N/2])
{
cout << x <<" is a mojority element "  <<endl;
return 0;
}
}
cout<<x<<" is not a majority element\n";
}```
```5 2
1 2 3 3 6```
`2 is not a majority element`

### Complexity Analysis

Time Complexity: O(N) because we just traverse the half sub-array which is lead us to O(n) time complexity.

Space Complexity: O(1) because here we don’t use any auxiliary space.

References

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions Core Java Interview Questions