#### 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:

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`

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

[TABS_R id=1515]

[forminator_quiz id=”1526″]

Space Complexity:`O(N)`

, for taking additional`Hash`

array.