Problem
In an instant runoff election, every voter ranks all the candidates. The count goes in rounds:
- Each ballot counts as one vote for its highest-ranked candidate who is still in the race.
- If a candidate has more than half of all ballots, that candidate wins.
- Otherwise, if every remaining candidate has the same number of votes, they are all tied and the election ends.
- Otherwise, every remaining candidate with the fewest votes is eliminated (all of them at once if several share the lowest count), and a new round starts.
Implement runoff_election(candidates, ballots).
Input
candidates: The candidates' names. Candidate i is candidates[i].
ballots: One row per voter: the candidate numbers (0-based) from most preferred to least preferred. Each row lists every candidate exactly once.
Output
Return a list with the winner's name, or, if the election ends in a tie, the names of all tied candidates in the order they appear in candidates. With no ballots, all candidates are tied.
Constraints
1 ≤ length of candidates ≤ 9
0 ≤ number of ballots ≤ 200
Examples
Input:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
Expected output:
expected = ["Ana"]
Input:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 2, 1},
{1, 2, 0},
{1, 0, 2},
{2, 0, 1}
};
Expected output:
std::vector<std::string> expected = {"Ana"};
Input:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 2, 1},
new long[] {1, 2, 0},
new long[] {1, 0, 2},
new long[] {2, 0, 1}
};
Expected output:
string[] expected = new string[] {"Ana"};
Explanation
Round 1: Ana 2, Bo 2, Cy 1; nobody has more than 2.5, so Cy is out. Cy's ballot moves to Ana, who wins with 3 of 5: ["Ana"].
Input:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
Expected output:
expected = ["Ana", "Bo", "Cy"]
Input:
std::vector<std::string> candidates = {"Ana", "Bo", "Cy"};
std::vector<std::vector<long long>> ballots = {
{0, 1, 2},
{0, 1, 2},
{1, 2, 0},
{1, 2, 0},
{2, 1, 0},
{2, 1, 0}
};
Expected output:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
Input:
string[] candidates = new string[] {"Ana", "Bo", "Cy"};
long[][] ballots = new long[][] {
new long[] {0, 1, 2},
new long[] {0, 1, 2},
new long[] {1, 2, 0},
new long[] {1, 2, 0},
new long[] {2, 1, 0},
new long[] {2, 1, 0}
};
Expected output:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
Explanation
Every candidate has 2 first-place votes out of 6, so the three of them are tied: ["Ana", "Bo", "Cy"].
How to approach it
Try on your own first, then open one hint at a time.
Hint 1
Keep a true/false list of who is still in the race and recount from scratch every round.
Hint 2
A majority means votes × 2 greater than the number of ballots.
Hint 3
Find the lowest count among remaining candidates only; if everyone remaining has it, the election is a tie.
Expected complexity
O(c^2 × b) time, O(c) extra space
References
This challenge is adapted for CodeUtility. Follow the statement and constraints above.