Missing number (XOR)

n numbers are drawn from 0..n with one value missing. Find it by XORing indices and values together.

The idea

The numbers 0..n XORed together, with every present value also XORed in, would cancel every value that appears in both lists, since x ^ x = 0. Only the missing number from 0..n, which has no partner in the array, survives. Folding in the index i instead of a separate range loop gets both lists XORed in one pass.

Code

public static int MissingNumber(int[] a) {
    int n = a.Length;
    int result = n;
    for (int i = 0; i < n; i++)
        result ^= i ^ a[i];
    return result;
}

Tips

• Starting result at n instead of 0 accounts for the one index (n itself) that the loop never reaches.
• This avoids the overflow risk of sum(0..n) - sum(a) on very large inputs.

In the .NET library

The same cancel-in-pairs idea powers Single number: here the pairs are (index, value) instead of (duplicate, duplicate).