Given:

- array a[1:N] consisting of integer elements in the range 1:N

Is there a way to detect whether the array is a permutation (no duplicates) or whether it has any duplicate elements, in O(N) steps and O(1) space without modifying the original array?

**clarification:** the array takes space of size N but is a given input, you are allowed a fixed amount of additional space to use.

The stackoverflow crowd has dithered around enough to make me think this is nontrivial. I did find a few papers on it citing a problem originally stated by Berlekamp and Buhler (see "The Duplicate Detection Problem", S. Kamal Abdali, 2003)

6more comments