Problem Statement:
You are given an array 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> //visit www.ProDeveloperTutorial.com for 450+ solved questions #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