Restated from stackoverflow:

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)

Restated from stackoverflow:

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)

Restated from stackoverflow:

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?

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)

Restated from stackoverflow:

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)