# Check if an array has a majority element

Given an array, the task is to find if the input array contains a majority element or not. An element is

Examples:

```Input : arr[] = {2, 3, 9, 2, 2}
Output : Yes
A majority element 2 is present in arr[]

Input  : arr[] = {1, 8, 9, 2, 5}
Output : No
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

A simple solution is to traverse through array. For every element, count its occurrences. If count of occurrence of any element becomes n/2, we return true.

An efficient solution is to use hashing. We count occurrences of all elements. If count becomes n/2 or more return true.

Below is the implementation of the approach.

## C++

 `// Hashing based C++ program to find if there ` `// is a majority element in input array. ` `#include ` `using` `namespace` `std; ` ` `  `// Returns true if there is a majority element ` `// in a[] ` `bool` `isMajority(``int` `a[], ``int` `n) ` `{ ` `    ``// Insert all elements in a hash table ` `    ``unordered_map<``int``, ``int``> mp; ` `    ``for` `(``int` `i = 0; i < n; i++)  ` `        ``mp[a[i]]++; ` `     `  `    ``// Check if frequency of any element is ` `    ``// n/2 or more. ` `    ``for` `(``auto` `x : mp) ` `      ``if` `(x.second >= n/2) ` `          ``return` `true``; ` `    ``return` `false``; ` `} ` ` `  `// Driver code ` `int` `main() ` `{ ` `    ``int` `a[] = { 2, 3, 9, 2, 2 }; ` `    ``int` `n = ``sizeof``(a) / ``sizeof``(a[0]); ` `    ``if` `(isMajority(a, n)) ` `        ``cout << ``"Yes"``; ` `    ``else` `        ``cout << ``"No"``; ` `    ``return` `0; ` `} `

## Java

 `// Hashing based Java program ` `// to find if there is a ` `// majority element in input array. ` `import` `java.util.*; ` `import` `java.lang.*; ` `import` `java.io.*; ` ` `  `class` `Gfg ` `{ ` `    ``// Returns true if there is a ` `    ``// majority element in a[] ` `    ``static` `boolean` `isMajority(``int` `a[], ``int` `n) ` `    ``{ ` `        ``// Insert all elements  ` `        ``// in a hash table ` `        ``HashMap mp = ``new`  `                            ``HashMap(); ` `         `  `        ``for` `(``int` `i = ``0``; i < n; i++)  ` `         `  `            ``if` `(mp.containsKey(a[i])) ` `                ``mp.put(a[i], mp.get(a[i]) + ``1``); ` `         `  `            ``else` `mp.put(a[i] , ``1``); ` `         `  `        ``// Check if frequency of any ` `        ``// element is n/2 or more. ` `        ``for` `(Map.Entry x : mp.entrySet()) ` `            `  `            ``if` `(x.getValue() >= n/``2``) ` `                ``return` `true``; ` `        ``return` `false``; ` `    ``} ` `     `  `    ``// Driver code ` `    ``public` `static` `void` `main (String[] args) ` `    ``{ ` `        ``int` `a[] = { ``2``, ``3``, ``9``, ``2``, ``2` `}; ` `        ``int` `n = a.length; ` `         `  `        ``if` `(isMajority(a, n)) ` `            ``System.out.println(``"Yes"``); ` `        ``else` `            ``System.out.println(``"No"``); ` `    ``} ` `} ` ` `  `// This code is contributed by Ansu Kumari `

## Python3

 `# Hashing based Python  ` `# program to find if ` `# there is a majority  ` `# element in input array. ` ` `  `# Returns true if there  ` `# is a majority element ` `# in a[] ` `def` `isMajority(a): ` `     `  `    ``# Insert all elements  ` `    ``# in a hash table ` `    ``mp ``=` `{} ` `     `  `    ``for` `i ``in` `a: ` `        ``if` `i ``in` `mp: mp[i] ``+``=` `1` `        ``else``: mp[i] ``=` `1` `     `  `    ``# Check if frequency  ` `    ``# of any element is ` `    ``# n/2 or more. ` `    ``for` `x ``in` `mp: ` `        ``if` `mp[x] >``=` `len``(a)``/``/``2``: ` `            ``return` `True` `    ``return` `False` ` `  `# Driver code ` `a ``=` `[ ``2``, ``3``, ``9``, ``2``, ``2` `] ` ` `  `print``(``"Yes"` `if` `isMajority(a) ``else` `"No"``) ` ` `  `#This code is contributed by Ansu Kumari `

Output:1

```Yes
```

## tags:

Arrays Searching Arrays Searching