Find the Winner
Posted: 17 Jan, 2021
Difficulty: Easy
You have been given an array/list of “VOTES” which contains the name of the candidates where each entry represents the name of the candidate who got the vote.
You are supposed to find the name of the candidate who received the maximum number of votes. If there is a tie, then print the lexicographically smaller name.
Input Format :
The first line contains an integer ‘T’ denoting the number of test cases. Then each test case follows.
The first input line of each test case contains an integer ‘N’ denoting the total number of votes cast.
Each of the next ‘N’ lines contains the name of the candidate who received the vote.
Output Format :
For each test case, print the name of the candidate who received the maximum number of votes.
Print the output of each test case in a separate line.
Note:
You are not required to print the expected output; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 50
1 <= ‘N’ <= 10^3
1 <= |NAME| <= 20
Where ‘N’ is the number of votes cast and |NAME| denotes the length of the candidate’s name.
Time Limit: 1 sec
Approach 1
The basic idea of this approach is to iterate through each candidate and count the number of votes he/she has received. We will keep track of the candidate with maximum votes.
Here is the algorithm :
- Create a variable “WINNER” which stores the name of the winning candidate and also create a variable “MAXVOTE” which stores the count of the vote the winning candidate has received.
- Iterate through the given array/list of votes using a variable ‘I’.
- Create a nested loop to count the number of votes the candidate has received.
- Update the “WINNER” and “MAXVOTE” if the current candidate has received more votes than the “MAXVOTE”. Also, in case “MAXVOTE” is equal to the votes received by the current candidate, update the “WINNER” as the lexicographically smaller name.
Approach 2
The basic idea of this approach is to use a HashMap to store the count of the votes received by each candidate.
Let unordered_map<string, int> getVotes which stores the votes received by a candidate.
Here is the algorithm:
- Create a variable “WINNER” that stores the name of the winning candidate and also create a variable “MAXVOTE” that stores the count of the vote the winning candidate has received.
- Iterate through the given array/list of votes using a variable ‘I’.
- Increment of the count of votes stored in the HashMap for the current candidate.
- Check whether the current candidate is the winner, i.e. if he has got more votes than the winning candidate.
- Update the “MAXVOTE” with the votes of the current candidate. And also update the “WINNER” to the name of the current candidate.
- Also, if “MAXVOTE” is equal to the current candidate’s votes, update the “WINNER” as the lexicographically smaller name.
SIMILAR PROBLEMS
One Odd Occurring
Posted: 17 Apr, 2022
Difficulty: Easy
Min Heap
Posted: 5 May, 2022
Difficulty: Moderate
Left Rotate an Array by One
Posted: 17 May, 2022
Difficulty: Easy
Largest Element in the Array
Posted: 17 May, 2022
Difficulty: Easy
Matrix Boundary Traversal
Posted: 20 May, 2022
Difficulty: Easy