Given an array of size N, find the majority element. The majority element is the element that appears more than 
times in the given array.
Examples:
Input: [3, 2, 3] Output: 3 Input: [2, 2, 1, 1, 1, 2, 2] Output: 2
The problem has been solved using 4 different methods in the previous post. In this post hashing based solution is implemented. We count occurrences of all elements. And if count of any element becomes more than n/2, we return it.
Hence if there is a majority-element, it will be the value of the key.
Below is the implementation of the above approach:
C++
#include<bits/stdc++.h> using namespace std; #define ll long long int // function to print the majority Number int majorityNumber(int arr[], int n) { int ans = -1; unordered_map<int, int>freq; for (int i = 0; i < n; i++) { freq[arr[i]]++; if (freq[arr[i]] > n / 2) ans = arr[i]; } return ans; } // Driver code int main() { int a[] = {2, 2, 1, 1, 1, 2, 2}; int n = sizeof(a) / sizeof(int); cout << majorityNumber(a, n); return 0; } // This code is contributed // by sahishelangia |
Java
import java.util.*; class GFG { // function to print the majority Number static int majorityNumber(int arr[], int n) { int ans = -1; HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>(); for (int i = 0; i < n; i++) { if(freq.containsKey(arr[i])) { freq.put(arr[i], freq.get(arr[i]) + 1); } else { freq.put(arr[i], 1); } if (freq.get(arr[i]) > n / 2) ans = arr[i]; } return ans; } // Driver code public static void main(String[] args) { int a[] = {2, 2, 1, 1, 1, 2, 2}; int n = a.length; System.out.println(majorityNumber(a, n)); } } // This code is contributed by Princi Singh |
Python3
# function to print the # majorityNumber def majorityNumber(nums): # stores the num count num_count = {} # iterate in the array for num in nums: if num in num_count: num_count[num] += 1 else: num_count[num] = 1 for num in num_count: if num_count[num] > len(nums)/2: return num return -1 # Driver Code a = [2, 2, 1, 1, 1, 2, 2] print(majorityNumber(a)) |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // function to print the majority Number static int majorityNumber(int []arr, int n) { int ans = -1; Dictionary<int, int> freq = new Dictionary<int, int>(); for (int i = 0; i < n; i++) { if(freq.ContainsKey(arr[i])) { freq[arr[i]] = freq[arr[i]] + 1; } else { freq.Add(arr[i], 1); } if (freq[arr[i]] > n / 2) ans = arr[i]; } return ans; } // Driver code public static void Main(String[] args) { int []a = {2, 2, 1, 1, 1, 2, 2}; int n = a.Length; Console.WriteLine(majorityNumber(a, n)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // function to print the majority Number function majorityNumber(arr, n) { let ans = -1; let freq = new Map(); for (let i = 0; i < n; i++) { freq[arr[i]]++; if(freq.has(arr[i])){ freq.set(arr[i], freq.get(arr[i]) + 1) }else{ freq.set(arr[i], 1) } if (freq.get(arr[i]) > n / 2) ans = arr[i]; } return ans; } // Driver code let a = [2, 2, 1, 1, 1, 2, 2]; let n = a.length; document.write(majorityNumber(a, n)); // This code is contributed // by _saurabh_jaiswal </script> |
Output
2
Complexity Analysis:
- Time Complexity : O(n)
- Auxiliary Space : O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
