Finding Duplicate Elements in an Array :: Phil! Gregory

Now, suppose that the array is of length n and only contains positive integers less than n. We can be sure (by the pigeonhole principle) that there is at least one duplicate.

Highlighted by taylortree

So, how do we find the beginning of the cycle? The easiest approach is to 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 a_i and a_j). At each step of the algorithm, move a_i one step along the sequence, but move a_j two steps. Stop when a_i = a_j.

Highlighted by taylortree