Last Updated on March 23, 2022 by Ria Pathak

### CONCEPTS USED:

Hashing

### DIFFICULTY LEVEL:

Medium

### PROBLEM STATEMENT`(`

SIMPLIFIED`)`

:

Given an array of size

`N`

, which contains the voting`ID's`

of students that have stood up for the elections for class monitor, the candidate with votes greater than half the strength of the class will become monitor, find the`ID`

of candidate that can become monitor else return`-1`

if no one can become.

**See original problem statement here**

#### For Example:

```
Input : A = [1, 3, 2, 2, 2]
Output : 2
Explanation : 2 got 3 votes which is greater than half the strength of the class i.e. 5/2 = 2.
```

### SOLVING APPROACH:

#### BRUTE FORCE METHOD:

- Run two loops, outer loop for selecting the voting
`ID`

and inner loop for counting its frequency, after the inner loop ends check if the frequency is greater than`Strength-of-class/2`

.- If
`Yes`

return this`ID`

, else check for all such`ID's`

. If no`ID`

wins the voting return`-1`

.`Time Complexity`

of this solution is`O(N^2)`

and is not an efficient approach in terms of time taken.

#### EFFICIENT METHOD:

The idea is to use

`Hashing`

. While traversing the array of`ID's`

keep incrementing the`count`

of votes for that particular`ID`

.If

`count`

of any`ID`

becomes greater than`Strength-of-class/2`

, simply return it. Else return`-1`

.

#### ILLUSTRATION:

```
A = [1, 3, 2, 2, 2]
hash[]
i = 0
hash[A[0]]++ => hash[1] = 1
i = 1
hash[A[1]]++ => hash[3] = 1
i = 2
hash[A[2]]++ => hash[2] = 1
i = 3
hash[A[3]]++ => hash[2] = 2
i = 4
hash[A[4]]++ => hash[2] = 3
Since, 3 > 5/2
Therefore, ID 2 with 3 votes wins the voting.
```

### SOLUTIONS:

#include <stdio.h> int main() { int t; scanf("%d", &t); while(t--){ int n; scanf("%d", &n); //storing frequency of votes in hash array int hash[1000000] = {0}; int arr[n]; int winner = -1; for(int i=0; i<n; i++){ scanf("%d", &arr[i]); hash[arr[i]]++; /* if frequency of votes becomes greater than half of total votes, this element is our winner */ if(hash[arr[i]] > n/2) winner = arr[i]; } printf("%d\n", winner); } return 0; }

#include <bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--){ int n; cin>>n; //storing frequency of votes in hash array int hash[1000000] = {0}; int arr[n]; int winner = -1; for(int i=0; i<n; i++){ cin>>arr[i]; hash[arr[i]]++; /* if frequency of votes becomes greater than half of total votes, this element is our winner */ if(hash[arr[i]] > n/2) winner = arr[i]; } cout<<winner<<"\n"; } return 0; }

import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t != 0){ int n = sc.nextInt(); //storing frequency of votes in hash array int hash[] = new int[1000000]; int arr[] = new int[n]; int winner = -1; for(int i=0; i<n; i++){ arr[i] = sc.nextInt(); hash[arr[i]]++; /* if frequency of votes becomes greater than half of total votes, this element is our winner */ if(hash[arr[i]] > n/2) winner = arr[i]; } System.out.println(winner); t--; } } }

[forminator_quiz id="1526"]

**Space Complexity**:

`O(N)`

, for taking additional `Hash`

array.
This article tried to discuss Hashing. Hope this blog helps you understand and solve the problem. To practice more problems on Hashing you can check out MYCODE | Competitive Programming.