Subscribe to the weekly news from TrueShelf

0

Read Once Promised Majority

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

Answers

0

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.

Related Content