Saturday, December 4, 2021
HomeTop Coding QuestionWrite a program to find the majority element.

# Write a program to find the majority element.

Given an integer array we have to find the majority element of array and print the result on screen.

so what is majority element of array?

An element is said to be majority element of array if it appears more than n/2 times in an array.

Example:

``````Input:5 5 2 3 1 5 5
output:5``````

Logic:

``````step 1-iterate whole array and initalise the variable count and max.
step 2-start traverse another loop
step 3-start checking if max is smaller than current count.
step 4- update the max value.``````

code:

```#include <bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n];
for(int i=0;i<n;i++)
{
cin>>a[i];
}
int k=-1;
int maxx = 0;
for (int i = 0;i< n;i++)
{
int cnt = 0;
for (int j=0; j<n; j++)
{
if (a[i]==a[j])
{
cnt++;
}
}
if(cnt>maxx)
{
maxx = cnt;
k = i;
}
}
int mid=n/2;
if (maxx>mid)
{
cout<<" majority element is "<<a[k]<<endl;
}
else
{
cout<<"Not exist!"<<endl;
}

}
```

Output:

``````input:
7
5 5 2 3 1 5 5

output:
majority element is 5``````

Time Complexity:O(N*N)

Space Complexity:O(1)