3
$\begingroup$

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?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Navjot Waraich Jul 18 '18 at 10:36
  • $\begingroup$ Also if i shift my range to 0 to n-1 and make total array elements equal to n, will it still work?? $\endgroup$ – Navjot Waraich Jul 18 '18 at 10:41
  • $\begingroup$ I'm not sure what you mean by "infinite loop". You always apply a cycle detection algorithm in the presence of a cycle. $\endgroup$ – Yuval Filmus Jul 18 '18 at 10:47
  • $\begingroup$ I'll you figure out any other variants. You've already seen the basic trick. $\endgroup$ – Yuval Filmus Jul 18 '18 at 10:48
  • 1
    $\begingroup$ I just ran the code on Wikipedia, and it worked on your example. $\endgroup$ – Yuval Filmus Jul 18 '18 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.