Single Number

How you get there

1. 1XOR is its own inverse, so x ^ x is 0.
2. 2XOR is commutative, so order does not matter.
3. 3XOR-ing everything cancels the pairs and leaves the single value.

Solution

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

Time

O(n)

Space

O(1)

What goes wrong

A hash map works but uses O(n) space, which the constraint usually forbids.