Problem of the Week 1198

Determine the Majority

Solution

Solutions to Problem 1198 were submitted by Stephen Morris, Mark Rickert, Yajie Zhang, Mengchen Xue, John Guilford, Stephen Meskin, and Dan Velleman, whose solution appears below. The solution is extremely simple, perhaps surprisingly so, but the reason it works is pretty clear.

Memorize the first name you hear and increment the counter. Then compare every name you hear to the memorized name; increment the counter if they agree; decrement if not.

If the counter ever gets to 0, start over: memorize the next name you hear and increment the counter, and continue as before. The name you have memorized at the end is the majority name. Reason: If the counter never gets back to 0, it is clear that the memorized name is the majority. If it ever gets to 0, then no name has a majority so far. (The memorized name has exactly half so far, and each of the other names have at most half.) So whatever name has a majority overall will have to have a majority in the remainder of the list. That's why starting over works.

Complete Mathematica code for the basic algorithm is just this:

F[X_] := (c=0; Do[ If[c==0,  S=L; c++, If[S ==L , c++, c--]], {L,X}]; S)

For a million-length list, this takes about one second. Note that it does not compute the number of times the majority appears.

What is happening is really very simple. Consider the string of 11 digits 13400024000 having 0 in the majority. The algorithm will reset in these spaces: 13    40    0024    000, leaving 0 in memory at the end, the point being that the discarded sequences do not affect the majority digit, and 0 is in the majority of the final triple 000.

[Back to Problem 1198]

© Copyright 2015 Stan Wagon. Reproduced with permission.


6 January 2015