Here’s a nice problem from

Notes on Streaming Algorithms:

Suppose we have sequence from a set , and that we know that one value from occurs **more** than times in the sequence; **find the most frequent value using only two variables having total memory of only bits and in only a single sweep.**

Spoiler 1

can store any value up to

.

Spoiler 2

can store any value from

.

Answer

Variables are

and

. Scan the list once, each element votes for

using

.

for each element
element == major? count++ : count--
if (count == 0)
major = element
count = 1

My implementation is in git and below.

*Related*