Subscribe to the weekly news from TrueShelf

## 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

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.