A club elects its president by a simple ballot: each vote is the member number of a candidate. This year one candidate is known to have received more than half of all votes.
Write majority_winner(votes) -> int that returns that candidate's number.
majority_winner([7, 3, 7, 7, 2]) # 7 (3 of 5 votes)
majority_winner([4]) # 4
majority_winner([-1, 5, 5, -1, -1]) # -1
Constraints:
1 <= len(votes) <= 2 * 10^5- Candidate numbers are integers in
[-10^9, 10^9]. - Exactly one candidate has more than
len(votes) / 2votes.
Counting the votes of each candidate by rescanning the whole list is O(n²). Aim for O(n) time.
Follow-up (not tested): can you find the winner with only O(1) extra memory?
Show hint
One pass that keeps a running tally for every candidate is enough; stop as soon as someone's tally passes half.