Single Number

Problem

You're given a list of integers where every number appears exactly twice except for one, which appears once. Find that one number, in linear time and constant extra space.

My notes

Signal

"Every element appears twice except one, find it in O(1) space" is the tell for XOR-cancels-pairs: a hash set would solve it but costs O(n) space, which is exactly what the problem is asking you to avoid.

Approach

XOR every number together. x ^ x == 0, so every paired value cancels itself out regardless of order, and x ^ 0 == x, so whatever's left after all the cancellation is the unpaired number. One pass, one accumulator, no memory of what you've seen.

Skeleton

result = 0
for x in nums:
    result ^= x
return result

Solution

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

Complexity

O(n) time — one pass over the array. O(1) space — a single accumulator, no hash set.

Pitfalls

Reaching for a Counter or hash set out of habit — correct, but O(n) space, which defeats the point when the interviewer asks for constant space as a follow-up.
This trick only works because exactly one element is unpaired and every other element appears an even number of times — if the follow-up changes to "every element appears three times except one," XOR alone no longer works and you need a different bitwise accumulator (counting bits mod 3 per position).