Single Number

Count occurrences

A frequency map stores each value beside the number of times it appears. Build one, then return the entry whose count is one. This follows the guarantee directly and makes a useful correctness oracle.

def single_number(nums: list[int]) -> int:
    counts: dict[int, int] = {}
    for value in nums:
        counts[value] = counts.get(value, 0) + 1
 
    for value, count in counts.items():
        if count == 1:
            return value
    raise ValueError("the input has no single value")

Time O(n). Space O(n) for the frequency map.

XOR fold

Exclusive OR (XOR) compares two integers bit by bit and sets a result bit when the input bits differ. Three identities do all the work here:

• value ^ value == 0
• value ^ 0 == value
• regrouping or reordering XOR operations doesn't change the result

Start from zero and XOR every value into one accumulator. Each duplicated value cancels its partner. The only value without a partner survives.

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

Negative integers need no special branch: identical bit patterns still cancel in pairs.

Time O(n). Space O(1) — one pass and one accumulator.