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