Posted by Mike Taylor | Monday, September 03, 2007
integers less than n. We can be sure (by the pigeonhole principle)
that there is at least one duplicate.
use Floyd's cycle-finding algorithm. It works roughly like this:
Start at the beginning of the sequence. Keep track of two values (call
them ai and aj). At
each step of the algorithm, move ai one step
along the sequence, but move aj two steps. Stop
when ai = aj.