[biobot]

This is the solution I posted there:

Called the missing number m, duplicate d.

The main idea is to find m+d and m-d. Then it’s trivial to find m and d.

1) Find n XOR d:

   X_array = 1;
   I_array = 1;

   for (i=2..N)

      X_array = X_array XOR A[i]; I_array = I_array XOR i;

   endfor

Then m XOR d = I_array XOR X_array

2) Find m – d

It will be a little bit more complicated. The idea is to get the sum of (1..N) subtract the sum of our array. But we have to be careful not to over or underflow the result.

   Diff = 0;

   i = j = 0; // i index I, j index A

   while (i < N) && (j < N)

     if (Diff + i < N-1)

         Diff = Diff + i;

         i++; //consume one in I

     else

         Diff = Diff – A[j];

         j++; // consume one in J

     endif

   end

// Need some corner case check here to but I will omit

3) So we have (m XOR d) and m – d. Also, note that m XOR d is basically m + d without the carry bit so it will be trivial to get m and d.

running time : 3 N <- can be squeeze to 2N if merge the two logic

space : O(1)

[pedrocr]

>note that m XOR d is basically m + d without the carry bit

This isn't true. XOR is addition without any carry bits so there are several solutions that have the same XOR and difference

[biobot]

There are at most 2 solutions: if m XOR d = a then either m+d = a or m+d = a+N.

With the combination of m-d = b, you will find m and d.

If both of them satisfied ( remember m and d are bounded by 1 and N) then we actually have two solutions.

[pedrocr]

Here's a counterexample.

Sequence is [1, 2, 3, 4, 6, 6, 7, 8, 9, 10] so m = 5 and d = 6

  diff = 5-6 = -1
  xor = 5^6 = 3

  1-2 = -1
  1^2 = 3

  5-6 = -1
  5^6 = 3

  9-10 = -1
  9^10 = 3

So three different combinations, within N, that obey the two constraints

[biobot]

OK. I think I find a way around.

Assume d XOR m = a. Find k = position of the first bit (from MSB to LSB) in a. Then d + m can be in [a + 2^(k+1),a + 2^(k+2),...,a + 2^63].

We will have less than 63 cases. In each case, after we find d and m, make sure they are in range and then linear test.

So in the end, we may need to run at most 63+3 = 66 N. But it still linear though.

[biobot]

Make sense!

That fails my solution!