[Restated from stackoverflow](https://stackoverflow.com/questions/2872959/algorithm-how-to-tell-if-an-array-is-a-permutation-in-on/2874631#2874631):


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](https://stackoverflow.com/questions/2872959/algorithm-how-to-tell-if-an-array-is-a-permutation-in-on/2874631#2874631))



duplicate detection problem
It's at least possible to test whether the input is a permutation with a randomized algorithm that uses O(1) space, always answers "yes" when it is a permutation, and answers "yes" incorrectly when it is not a permutation only with very small probability.


Simply pick a hash function $h(x)$, compute $\sum\_{i=1}^n h(i)$, compute $\sum\_{i=1}^n h(a[i])$, and compare the two sums.


Ok, some care needs to be used in defining and choosing among an appropriate family of hash functions if you want a rigorous solution (and I suppose we do want one, since we're on mathoverflow not stackoverflow). Probably the simplest way is just to fill another array $H$ with random numbers and let $h(x)=H[x]$, but that is unacceptable because it uses too much space. I'll leave this part as unsolved and state this as a partial answer rather than claiming full rigor at this point.


See also my paper [Space-Efficient Straggler Identification in Round-Trip Data Streams via Newton's Identitities and Invertible Bloom Filters](http://arxiv.org/abs/0704.3313) which solves a more general problem (if there are O(1) duplicates, say which ones are duplicated, using only O(1) space) with the same lacuna in how the hash functions are defined. It also contains a proof that an algorithm that makes only a single pass over the data cannot solve the problem exactly and deterministically, but of course that doesn't apply to algorithms with random access to the input array.


