8 Responses to “Find the Duplicate”

1. Dan Says:
   October 14th, 2007 at 11:44 pm

   Just to clear away the confusion, my solution uses O(1) integer variables, each of which indeed requires log(N) memory because we want it to have values up to N. I didn’t take that fine point into account in my previous comment.

   Let us assume the indices of the vector start with 0, and let us denote the i-th element of the vector v[i]. An algorithm, in C code:

   int i, d, x, y;
   for(i=0, x=0; i1. We start traversing the graph from node 0 and always leaving by the available edge. Eventually (and quite importantly, after traversing N edges at the most), we will revisit a previous node. Let us look at the first node to be revisited: It is not 0, as we cannot enter 0. Thus, we have entered it twice, and from two different nodes, because it is the first to be revisited – so it is a duplicate. Furthermore, if we continue traversing the graph, we will necessarily walk in a cycle [Note: this is related to the hint]. The first loop traverses N edges of the graph, therefore ending inside the aforementioned cycle. Using that knowledge, the second loop calculates the length/period of the cycle, and stores that in d. The third loop then sets y to the d-th element to be visited in the normal walk, and x is set to 0, the beginning of the walk. The fourth loop then traverses the graph with both x and y simultaneously, knowing that they will be equal iff x is in the cycle, because they are always a distance of d off. Therefore when they first become equal, we have found the first element of the cycle, which is our duplicate.

2. Dan Says:
   October 14th, 2007 at 11:51 pm

   It appears that I was not careful enough not to use the lesser-than sign, and some parts got cut off.

   int i, d, x, y;
   for(i=0, x=0; i!=N; i++, x=v[x]);
   for(d=1, y=v[x]; y!=x; d++, y=v[y]);
   for(i=0, y=0; i!=d; i++, y=v[y]);
   for(x=0; x!=y; x=v[x], y=v[y]);
   return x;

   Start of Explanation:

   We think of the vector as directed graph, with nodes 0, … , N-1, and each node i has exactly one edge leaving it, and entering node v[i]. In particular, no edge enters node 0, and a node is a duplicate element iff its entering degree is greater than 1. [The rest of the explanation continues above]

3. yaniv Says:
   October 15th, 2007 at 12:03 am

   Dan,

   I am very sorry that comment got cut-off by the stupid html filtering mechanism I am using. It removes everything between the < and the > signs.

   Please use the symbols: ampersand, ‘l’, ‘t’, and semicolon (4 symbol all together) for the < sign. The > sign can be used regularly.

   The solution is really cool.

   In a slightly different situation, if you knew that a cycle existed and had good reason to suspect that its length (and the length of the tail leading to it) is << N (wow! almost got my comment cut-off there… ) then instead of performing the initial step N times (which is of course the logical thing to do in this riddle where you cannot make the previous assumption) you could start with x = 0 and y = 0 and each turn advance x by one step and advance y by 2 steps. When x == y, you will know that you are inside the cycle. Pollard’s Rho algorithm (used mainly for factoring) uses this technique.

Leave a Reply

Name (required)

Mail (will not be published) (required)

Website

Notify me of followup comments via e-mail