Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

Last Updated on March 23, 2022 by Ria Pathak

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

### SOLVING APPROACH:

#### BRUTE FORCE METHOD:

1. 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[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.