Given an array of size
N, which contains the voting
ID'sof 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
IDof candidate that can become monitor else return
-1if no one can become.
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:
Refer some websites to learn coding and Run two loops, outer loop for selecting the voting
IDand inner loop for counting its frequency, after the inner loop ends check if the frequency is greater than
ID, else check for all such
ID's. If no
IDwins the voting return
Time Complexityof this solution is
O(N^2)and is not an efficient approach in terms of time taken.
The idea is to use
Hashing. While traversing the array of
ID'skeep incrementing the
countof votes for that particular
IDbecomes greater than
Strength-of-class/2, simply return it. Else return
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.
O(N), for taking additional