Majority Votes

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:

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

Previous post Find Mountain Top
Next post Files

Leave a Reply

Your email address will not be published. Required fields are marked *