[biobot]

One of my friend came up with this solution:

m is missing,d is duplicate. I is 1..N, A is input.

Step 1: Compute m XOR d by XOR all values of A and I together. let say x = m XOR d. Then x must has at least one 1 bit (or else m == d). Call the bit p. So now we can separate A into two list A0 are those with bit p == 0 and A1 are those with bit p == 1. So we have separated m and d into two different list.

Step 2: Iterate through I, maintain two number x0 and x1 as the results of XOR operations of those elements with p bit == 0 and == 1 respectively. Do the same for A to get a0 and a1. Then we know that m is either a0 XOR x0 or a1 XOR x1. One more linear test in A to confirm the missing element m.

In the end, the running time can be squeezed into 2 N. space = O(1).