The XOR trick works in two passes with a read-only array.
This avoids the problem of possible integer overflows which the sum and sum of squares solution has.
Let the two numbers be
y, one of which is the missing number and the other repeated.
XOR all the elements of the array, along with
The result is
w = x XOR y.
y are distinct,
w is non-zero.
Pick any non-zero bit of
y differ in this bit. Say the position of the bit is
Now consider a split of the array (and the numbers
1,2,...,N) into two sets, based on whether the bit at position k is 0 or 1.
Now if we compute the XOR (separately) of the elements of the two sets, the result has to be
Since the criteria for splitting is just checking if a bit is set of not, we can compute the two XORs of the two sets by making another pass through the array and having two variables, each of which holds the XOR of the elements seen so far (and
1,2,...N), for each set. At the end, when we are done, those two variables will hold