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.

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)

Implementation

SolutionTestsChallenge

single_number

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.

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)

single_number

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

Source code in src/algo/bit_manipulation/single_number.py

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
    return result

tests/bit_manipulation/test_single_number.py

"""Tests for single number."""

from hypothesis import given
from hypothesis import strategies as st

from algo.bit_manipulation.single_number import single_number


class TestSingleNumber:
    def test_basic(self) -> None:
        assert single_number([4, 1, 2, 1, 2]) == 4

    def test_single_element(self) -> None:
        assert single_number([1]) == 1

    def test_negative_numbers(self) -> None:
        assert single_number([-1, 2, -1]) == 2

    def test_zero_is_single(self) -> None:
        assert single_number([0, 3, 3]) == 0

    def test_larger_array(self) -> None:
        assert single_number([5, 3, 5, 3, 7]) == 7

    @given(
        unique=st.integers(min_value=-1000, max_value=1000),
        pairs=st.lists(
            st.integers(min_value=-1000, max_value=1000),
            min_size=0,
            max_size=20,
        ),
    )
    def test_always_finds_unique(self, unique: int, pairs: list[int]) -> None:
        nums = [unique]
        for p in pairs:
            if p == unique:
                continue
            nums.extend([p, p])
        assert single_number(nums) == unique

Implement it yourself

Run: just challenge bit_manipulation single_number

Then implement the functions to make all tests pass. Use just study bit_manipulation for watch mode.

Reveal Solution

single_number

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.

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)

single_number

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

Source code in src/algo/bit_manipulation/single_number.py

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
    return result