Single Number

Problem

Given a non-empty array where every element appears twice except for one, find that single element.

Approach

XOR all elements. Since a ^ a = 0 and a ^ 0 = a, all pairs cancel out, leaving only the single element. Alternate single_number_reduce folds the same XOR with functools.reduce.

When to Use

XOR uniqueness — "find the element appearing once while others appear twice". XOR cancels pairs: a ^ a = 0. Extends to "two unique numbers" by splitting on a differing bit. Keywords: "unique", "missing", "duplicate".

Complexity

Time	O(n)
Space	O(1)

Source

"""Single Number — find the element appearing once (others twice).

Problem:
    Given a non-empty array where every element appears twice except
    for one, find that single element.

Approach:
    XOR all elements. Since a ^ a = 0 and a ^ 0 = a, all pairs
    cancel out, leaving only the single element. Alternate
    single_number_reduce folds the same XOR with functools.reduce.

When to use:
    XOR uniqueness — "find the element appearing once while others appear
    twice". XOR cancels pairs: a ^ a = 0. Extends to "two unique numbers"
    by splitting on a differing bit. Keywords: "unique", "missing", "duplicate".

Complexity:
    Time:  O(n)
    Space: O(1)
"""

from collections.abc import Sequence
from functools import reduce
from operator import xor


def single_number(nums: Sequence[int]) -> int:
    """Return the element that appears exactly once.

    >>> single_number([4, 1, 2, 1, 2])
    4
    >>> single_number([1])
    1
    """
    result = 0
    for n in nums:
        result ^= n  # a^a=0 cancels pairs, a^0=a preserves the single value
    return result


# --- functools.reduce alternate: fold XOR across the sequence (stdlib idiom) ---
def single_number_reduce(nums: Sequence[int]) -> int:
    """Return the element that appears exactly once, via functools.reduce.

    >>> single_number_reduce([4, 1, 2, 1, 2])
    4
    >>> single_number_reduce([1])
    1
    """
    return reduce(xor, nums, 0)