Single number (XOR)

Every value appears twice except one. Find the odd one out without a dictionary.

Time O(n)Space O(1)Code C++, Python and C#

Watch it animatedStep through it, with the running line highlighted. Free with an account.

The idea

XOR has two useful properties: x ^ x = 0 and x ^ 0 = x, and the order does not matter. XOR everything together and each pair cancels itself out, leaving the single value.

Code

C++PythonC#

int singleNumber(const vector<int>& a) {
    int result = 0;
    for (int x : a)
        result ^= x;
    return result;
}

def single_number(a: list[int]) -> int:
    result = 0
    for x in a:
        result ^= x
    return result

public static int SingleNumber(int[] a) {
    int result = 0;
    foreach (int x in a)
        result ^= x;
    return result;
}

Tips

Watch the result bits: a bit flips on when a value first appears and flips back off when its twin arrives.
The same trick swaps two integers without a temporary variable.

In the .NET library

a.Aggregate(0, (acc, x) => acc ^ x) is the LINQ one-liner for the same fold.