समस्या
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.
सीमाएँ
1 ≤ length of candidates ≤ 9
0 ≤ number of ballots ≤ 200
उदाहरण
इनपुट:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 2, 1],
[1, 2, 0],
[1, 0, 2],
[2, 0, 1]
]
अपेक्षित आउटपुट:
expected = ["Ana"]
इनपुट:
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}
};
अपेक्षित आउटपुट:
std::vector<std::string> expected = {"Ana"};
इनपुट:
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}
};
अपेक्षित आउटपुट:
string[] expected = new string[] {"Ana"};
व्याख्या
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"].
इनपुट:
candidates = ["Ana", "Bo", "Cy"]
ballots = [
[0, 1, 2],
[0, 1, 2],
[1, 2, 0],
[1, 2, 0],
[2, 1, 0],
[2, 1, 0]
]
अपेक्षित आउटपुट:
expected = ["Ana", "Bo", "Cy"]
इनपुट:
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}
};
अपेक्षित आउटपुट:
std::vector<std::string> expected = {"Ana", "Bo", "Cy"};
इनपुट:
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}
};
अपेक्षित आउटपुट:
string[] expected = new string[] {"Ana", "Bo", "Cy"};
व्याख्या
Every candidate has 2 first-place votes out of 6, so the three of them are tied: ["Ana", "Bo", "Cy"].
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
Keep a true/false list of who is still in the race and recount from scratch every round.
संकेत 2
A majority means votes × 2 greater than the number of ballots.
संकेत 3
Find the lowest count among remaining candidates only; if everyone remaining has it, the election is a tie.
अपेक्षित जटिलता
O(c^2 × b) time, O(c) extra space
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।