Loading...
Loading...
Loading...
In a class representative election, each of the n students writes one candidate ID on a slip. A candidate wins outright only with more than half of all the votes.
Print the winner's ID. If no candidate has more than half the votes, print -1. Try to use only a few variables besides the list of votes.
-1.Example 1
Input
7 2 2 1 1 2 2 3
Output
2
Candidate 2 has 4 of the 7 votes, which is more than half.
Example 2
Input
4 5 5 6 6
Output
-1
Candidate 5 has 2 of 4 votes. Exactly half is not enough.
Try the problem first. Open one hint at a time.
If a winner exists, its votes outnumber all the other votes put together.
Pair each vote with a vote for a different candidate and cancel both. A winner can never be fully cancelled.
Keep a candidate and a count. A matching vote adds 1, a different vote takes away 1, and at 0 the next vote becomes the new candidate.
The candidate left at the end is only a suspect. Count its votes in a second pass to check it really has more than n / 2.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor