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
Posted: Jun 06 '12
Seen: 134 times
Last updated: Aug 04 '12
