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)