Subscribe to the weekly news from TrueShelf

Suppose the input is $n$ numbers from $1$ to $n$, separated by commas and we know that one of the number occurs more than $n/2$ times. How can we decide which if we can read the input tape only once (from left to right) and we also have a work tape of size $O(\log n)$?

Example input: 11,101,11,110,101,101,101

Keep a pair of integers (i,c) initialized to (0,0) on the work tape. (i is our current candidate for the majority element, and c is a count)

While(read x):
if(c==0)
i=x; c=1;
else if(i==x)
c++;
else
c--;
return i;


The above algorithm basically cancels out pairs of distinct numbers from left to right. It is clear that the remaining number must be the majority element.

0

0

0

0

0

0

0

0

0

0