Hashing

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.``````

#### BRUTE FORCE METHOD:

1. Refer some websites to learn coding and 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`.

2. If `Yes` return this `ID`, else check for all such `ID's`. If no `ID` wins the voting return `-1`.

3. `Time Complexity` of this solution is `O(N^2)` and is not an efficient approach in terms of time taken.

#### EFFICIENT METHOD:

1. The idea is to use `Hashing`. While traversing the array of `ID's` keep incrementing the `count` of votes for that particular `ID`.

2. 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]++ => hash = 1

i = 1
hash[A]++ => hash = 1

i = 2
hash[A]++ => hash = 1

i = 3
hash[A]++ => hash = 2

i = 4
hash[A]++ => hash = 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 = {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 = {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;
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--;
}
}
}
```

Space Complexity: `O(N)`, for taking additional `Hash` array.