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$
0

1 Answer 1

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$
6
  • $\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$ Commented Jul 18, 2018 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$ Commented Jul 18, 2018 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$ Commented Jul 18, 2018 at 10:47
  • $\begingroup$ I'll you figure out any other variants. You've already seen the basic trick. $\endgroup$ Commented Jul 18, 2018 at 10:48
  • 1
    $\begingroup$ I just ran the code on Wikipedia, and it worked on your example. $\endgroup$ Commented Jul 18, 2018 at 11:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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