Loading...
Loading...
Loading...
Students vote for a class monitor by writing a candidate number. A candidate wins only with a majority: more than half of all votes. Print the winner, or NO MAJORITY.
There can be up to 10^5 votes and candidate numbers up to 10^9, so counting votes for every candidate number is not possible.
NO MAJORITY.Example 1
Input
7 3 1 3 3 2 3 3
Output
3
3 has 5 of 7 votes, more than half.
Example 2
Input
6 4 4 4 5 5 5
Output
NO MAJORITY
3 of 6 is exactly half, which is not more than half.
Try the problem first. Open one hint at a time.
Pair off two different votes and throw both away: a true majority still has votes left at the end.
Keep a candidate and a count. If count is 0, take the current vote as the candidate. Add 1 for the same vote, subtract 1 for a different one.
The candidate left at the end is only a suspect. Count its votes in a second pass and check it is more than n / 2.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor