Loading page…
Practice problem · easy
A polling app draws each option as a bar. When two options have exactly the same number of votes, their bars tie, and the app must add a tiebreak note under the poll.
Before it draws a poll, the app checks whether any two options share a tally. You receive the votes in the order they arrived. Each vote is the id of the option that the voter chose.
Write all_tallies_differ(votes).
votes[i] is the id of the option chosen by the i-th voter.true when no two options have the same tally. Return false when at least two options tie.true.Input: votes = [4, 7, 4, 9, 7, 4]
Output: trueThe trace counts the votes for each option, then looks at the tallies.
| Step | Read | Tallies after |
|---|---|---|
| 1 | option 4 | 4: 1 |
| 2 | option 7 | 4: 1, 7: 1 |
| 3 | option 4 | 4: 2, 7: 1 |
| 4 | option 9 | 4: 2, 7: 1, 9: 1 |
| 5 | option 7 | 4: 2, 7: 2, 9: 1 |
| 6 | option 4 | 4: 3, 7: 2, 9: 1 |
| 7 | check | tallies 3, 2, 1 are all different |
Option 4 has 3 votes, option 7 has 2 and option 9 has 1. No two tallies match, so the output is true.
Input: votes = [1, 2, 1, 2, 3]
Output: falseOptions 1 and 2 both have 2 votes, so they tie.
Input: votes = []
Output: trueNobody voted, so there are no options to tie.
0 ≤ votes.length ≤ 100,000 (votes in one poll)1 ≤ votes[i] ≤ 10^6 (option ids)Counting each option by scanning all the votes costs n steps for each option. A poll can have up to n options, so that is n × n, which is 10^10 steps and far over the budget of about 10^8 a second. A table of tallies is built in n steps, and the tallies are checked in at most n more.
all_tallies_differ · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.