The Majority Name

In a long list of names, one of the names appears more than half of the time. You will be read the names one at a time, without knowing how many they are, and without being able to write them down. If you have a very weak memory, how can you figure out which is the majority name?

SOLUTION

Remember the first name and then keep track of whether it has been repeated more than half of the time. To do that, simply add 1 if you hear the name or subtract one when you hear another name. If the list finishes and your counter is positive, then the first name is the majority. If your counter drops to 0, simply restart the procedure with the next name you hear.

This algorithm, invented by R. Boyer and J. Moore, works, because if the counter ends up at 0, then each of the names up to that moment has been read at most half of the time. Therefore, the majority name appears more than half of the time in the remainder of the list.

Unknown Author

We do not know where this puzzle originated from. If you have any information, please let us know via email.

Unknown Author

Puzzle Newsletter