Finding duplicate in immutable array in linear time and constant space

Question

We have a array of $N$+1 integers. The integers range from 1 to $N$. The array contains at least one duplicate. Our goal is to find one of the duplicate entries. We have the constraint that we cannot modify the input array. Is there any solution to this problem which has $O(N)$ time complexity and $O(1)$ space complexity?

Answer 1

Let us denote the array by $a_1,\ldots,a_{n+1}$. Define a function from $\{1,\ldots,n+1\}$ to itself as follows: $f(i) = a_i$. The graph of the function is a directed graph in which each node has outdegree 1. Since $n+1$ has indegree 0, the connected component of $n+1$ has a node with indegree 2, which corresponds to a duplicate entry. This node can be found using a cycle detection algorithm in linear time and constant space.

• Navjot Singh: If i use Floyd's cycle detection algorithm and array is {2, 2, 1}, we will fall in an infinite loop. What to do in this case.
• Navjot Singh: Also if i shift my range to 0 to n-1 and make total array elements equal to n, will it still work??
• Yuval Filmus: I'm not sure what you mean by "infinite loop". You always apply a cycle detection algorithm in the presence of a cycle.
• Yuval Filmus: I'll you figure out any other variants. You've already seen the basic trick.
• Yuval Filmus: I just ran the code on Wikipedia, and it worked on your example.