TopCoder problem "InstantRunoffVoting" used in SRM 393 (Division I Level One , Division II Level Two)

Problem Statement


Instant run-off voting is a system for selecting the most preferred candidate in an election. At the beginning of the process, each voter ranks the candidates from most preferred to least preferred. A series of automated voting rounds are then held to determine the overall winner.

In each round, each voter casts a single vote for his most preferred remaining candidate. If a candidate receives strictly more than 50% of the votes cast in that round, that candidate is declared the winner of the election. Otherwise, the candidate with the fewest votes in that round is eliminated, and another round is held. If multiple candidates are tied for the least number of votes, they are all eliminated. If all the candidates are eliminated, the election ends without a winner.

You are given the preferences of the voters in an election, and you must determine the outcome. There are N candidates numbered 0 to N-1, inclusive. The preferences are given in a String[] voters, where each element describes the preferences of a single voter. This is a permutation of the digits 0 to N-1 in decreasing order of preference. In other words, the first digit is the voter's most preferred candidate, the second digit is his second most preferred candidate, and so on. Return the number of the candidate who wins the election, or -1 if the election ends without a winner.



Method signature:int winner(String[] voters)
(be sure your method is public)


-voters will contain between 1 and 50 elements, inclusive.
-Each element of voters will contain between 1 and 10 characters, inclusive.
-Each element of voters will contain the same number of characters.
-Each element of voters will be a permutation of the digits between 0 and N-1, where N is the number of characters in each element of voters.


Returns: 0
In the first round, candidate 0 gets 3 votes and candidate 1 gets 2 votes, so candidate 0 wins.
Returns: 1
Nobody gets an absolute majority in the first round and candidate 2 is eliminated. Candidate 1 then receives 3 votes in the next round, giving an absolute majority.
Returns: -1
Each candidate gets 1 vote, so nobody can be declared winner.
Returns: -1
Candidate 0 is eliminated in the first round of voting. Candidate 2 is eliminated in the second round. In the third round, candidates 1 and 3 get 4 votes each. Neither candidate receives an absolute majority, and they are both eliminated for having the least number of votes, so the election ends without a winner.
Returns: 1
Returns: 9

Problem url:

Problem stats url:




PabloGilberto , Olexiy , gawry , ivan_metelsky

Problem categories: