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.

Your signal — what pointed here?Your skeleton — the reusable shape

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).