Sunday, June 20, 2021
Home coding Write 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)

LEAVE A REPLY

Please enter your comment!
Please enter your name here

- Advertisment -

Most Popular

Recent Comments