The number more than half
EasyStuck?
Show a hintHide the hint
Count each number and take the largest. Or keep one candidate and a tally, replacing the candidate whenever the tally hits zero.
The ideas behind this problem
Last problem in this lesson
Go to the next lessonOne number in the list appears more than half the time. Find it.
Worked example#
For [2, 2, 1, 1, 1, 2, 2] there are 7 numbers, so the answer appears at least 4 times:
| number | times |
|---|---|
| 2 | 4 |
| 1 | 3 |
So the answer is 2.
Counting with a hash map is the direct approach and is perfectly good.
There is also a clever one worth seeing, called Boyer-Moore voting. Keep a candidate and a count. If the count is zero, take the current number as the new candidate. Then add one if the current number matches the candidate, or subtract one if it does not. Because the majority number appears more often than everything else combined, it is the only one that can survive to the end.
Constraints#
1 <= n <= 100000- One number always appears more than n/2 times
Input
nums is a count then that many integers.
Output
The number that appears more than half the time.
Examples
Input
3 3 2 3
Output
3
3 appears twice out of three, which is more than half.
Input
7 2 2 1 1 1 2 2
Output
2
2 appears four times out of seven.
Input
1 1
Output
1
A single number is trivially the majority.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.