Find Majority Element of an Array
“Find Majority Element of an Array” is one of the most favorite technical interview problem based on array data structure. Here, we are given an array of size ‘n’ and our task is to find the majority element of the array.
If there is no majority Element, print a message “No majority element”.
A majority element of the array is the element which appears more than (n/2) elements.
Example (Find Majority Element of an Array):
INPUT: Arr[5] = {3, 1, 3, 2, 3} OUTPUT: 3 INPUT: Arr[5] = {1, 2, 3, 4, 5} OUTPUT: No majority element
There are many ways to find majority element of an array. Some of the ways are:
METHOD 1: Brute – force to Find majority element of an array
The steps required to find majority element of an array are as follows:
- Scan array size.
- Scan array elements.
- Now, count occurrence of each element of the array using two nested for loops.
- While counting occurrence of each element, also check if the count more than (n/2) or not. If for any element the count is more than (n/2), print the resultant element.
C++ Program to find majority element of an array is as follows:
/* Program to find the majority element of an array */
#include<bits/stdc++.h>
using namespace std;
int main()
{
/* Scan array size */
int n;
cout<<"Enter array size:";
cin>>n;
/*Scan array elements */
int arr[n];
cout<<"\nEnter array elements: ";
for(int i = 0; i < n; i++)
cin>>arr[i];
int res = -1;
/* Count frequency of each element */
for(int i = 0; i < n; i++)
{
int count = 0;
/* Count occurrence of each element of the array */
for(int j = 0; j < n; j++)
{
if(arr[i] == arr[j])
count++;
}
/* If count > (n/2), it's majority element */
if(count > (n/2))
{
res = arr[i];
break;
}
}
/* Print the result */
if(res == -1)
{
cout<<"\nNo majority element!!";
}
else
{
cout<<"\n"<<res<<" is majority element of the array!!";
}
}
OUTPUT: Enter array size: 5 Enter array elements: 1 2 3 2 3 No majority element!! Time Complexity: O(n^2), where ‘n’ is the size of the array
METHOD 2: Hashing Approach to find majority element of an array
The step required to find majority element of an array are as follows:
- Scan array size.
- Scan array elements.
- Create a hashmap as (key = int) and (value = int).
- Iterate over all the elements of the array and increment count of each element in map.
- Now, scan the map and check count of each element, whether it is greater than (n/2) or not. If any element has a count greater than (n/2), it will be majority element.
C++ Program to find majority element of an array is as follows:
/* Program to find the majority element of an array*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
/* Scan array size */
int n;
cout<<"Enter array size:";
cin>>n;
/*Scan array elements */
int arr[n];
cout<<"\nEnter array elements: ";
for(int i = 0; i < n; i++)
cin>>arr[i];
int res = -1;
/* Create hash map */
map<int,int> mp;
/* Store count of each element */
for(int i = 0; i < n; i++)
{
mp[arr[i]]++;
}
/* Check count of each element */
map<int,int> :: iterator itr;
for(itr = mp.begin(); itr != mp.end(); ++itr)
{
if(itr->second > (n/2))
{
res = itr -> first;
break;
}
}
/* Print the result */
if(res == -1)
cout<<"No majority element!!";
else
cout<<res<<" is the majority element!!";
}
OUTPUT: Enter array size: 5 Enter array elements: 2 1 2 3 2 2 is the majority element!! Time Complexity: O(nlogn) , n for scanning array and logn for searching and incrementing the count of each element.
Related Posts:
- Find Most Frequent Character of the String.
- Check Anagram Strings.
- Check Whether Given String is Palindromic Anagram or Not.
- Check Whether Given String is Panagram or Not.
- Find First Non-Repeating Character of the String.
- Find Most Frequent Element of the Array.
- Find Pair in an Array with Given Sum.
- Find First Repeating Element of an Array.
- Reverse a Linked List.
- Reverse a Linked List Using Stack.
- Printing Linked List in Reverse Order without actually reversing the Linked List.
- Swap Adjacent Elements of the Linked List.
- Count All Occurrences of a Particular Node in a Linked List.
- Bubble Sort on Linked List.
- Detect a Loop in a Linked List.
- Find the Length of the Loop present in the Linked List.
- Detect and Remove Loop from a Linked List.
- Segregate Even and Odd Nodes in a Linked List.
- Delete Complete Linked List.
- Delete Nth Node of the Linked List.