## Find the Duplicate

Dany Valevsky gave me this very cool riddle.

You are given a vector of size *N*, the elements of which are numbers in the range *1, …, N-1*. I.e. there is at least one repeating element. Give an algorithm that finds a repeating element (it does not matter which one, in case there are several) with *O(N)* time complexity and *O(1)* memory complexity.

NOTE - the time and memory complexities are calculated in integers. I.e. the input is of size *N*, not *N*log(N)*.