Problem Statement:
You are given an arrya of repeating elements. You need to find and print the majority element.
An element that appears more tha n/2 times, is called as majority element.
Example
Input : {3, 3, 4, 2, 4, 4, 2, 4, 4}
Output : 4
4 is repeated 5 times that is greater than the half of the size of the array.
Solution
Method 1: Brute Force Approach
Create 2 loops, and then keep track of the maximum count for all the different elements.
If the count become greater than n/2 times break the loop and return the element.
Method 2: Using hash map
A hashmap is a key value pair. Here the key is the element, and the value is the number of times the element is repeated.
Solution in C++
#include <algorithm>
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <unordered_map>
#include <queue>
using namespace std;
void find_majority_element_brute_force(int arr[], int n)
{
int maxCount = 0;
int index = -1;
for (int i = 0; i < n; i++)
{
int count = 0;
for (int j = 0; j < n; j++)
{
if (arr[i] == arr[j])
count++;
}
if (count > maxCount)
{
maxCount = count;
index = i;
}
}
if (maxCount > n / 2)
cout << "The majority element using brute force approach is "<< arr[index] << endl;
else
cout << "No Majority Element" << endl;
}
void find_majority_element_hash_map(int arr[], int size)
{
unordered_map<int, int> m;
for(int i = 0; i < size; i++)
m[arr[i]]++;
int count = 0;
for(auto i : m)
{
if(i.second > size / 2)
{
count =1;
cout << "The majority element using hash map approach is " << i.first<<endl;
break;
}
}
if(count == 0)
cout << "No Majority element" << endl;
}
int main()
{
int arr[] = { 1, 1, 2, 1, 3, 5, 1 };
int n = sizeof(arr) / sizeof(arr[0]);
find_majority_element_brute_force(arr, n);
find_majority_element_hash_map(arr, n);
return 0;
}
Output:
The majority element using brute force approach is 1
The majority element using hash map approach is 1