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.