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.