136. Single Number

Reformulated question¶

Find the only value that appears once in nums where every other value appears exactly twice, in \(O(n)\) time and \(O(1)\) extra space.

Example:

nums = [4,1,2,1,2] -> 4

Key trick¶

Use XOR.

a ^ a = 0
a ^ 0 = a
XOR is commutative and associative

So XORing all numbers cancels the pairs and leaves the single number.

Trap¶

Using a set or dict breaks the constant extra space requirement.
Sorting works but is \(O(n \log n)\), not linear.
Overcomplicating the scan instead of using the XOR identity.

Why is this question interesting?¶

It tests whether you recognize a bit-manipulation invariant and can turn constraints into the solution.

Solve the problem with idiomatic python¶

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        # XOR of equal numbers cancels to 0,
        # so only the unique number remains.
        # - a ^ a = 0
        # - a ^ 0 = a
        # - XOR is commutative and associative
        acc = 0
        for n in nums:
            acc ^= n
        return acc

Pytest test¶

import pytest


@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([1], 1),
        ([2, 2, 1], 1),
        ([4, 1, 2, 1, 2], 4),
        ([1, 2, 3, 1, 2], 3),
        ([0, 0, -1], -1),
        ([-3, 7, 7, -3, 9], 9),
        ([10, 5, 10], 5),
    ],
)
def test_single_number(nums, expected):
    assert Solution().singleNumber(nums) == expected

Comment my solution¶

Your solution does return the right answer on typical cases, but it misses the required space bound.

It uses a set, so extra space is \(O(n)\), not \(O(1)\).
The two-ended scan is unnecessary complexity for a problem with a one-line invariant.
The midpoint special-case makes the code harder to reason about.
XOR is the intended direct solution and is both simpler and optimal.

import pytest

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        nums_len = len(nums)
        mid = len(nums) // 2
        seen = set()
        for i in range(mid):
            n = nums[i]
            m = nums[nums_len - 1 - i]
            if n in seen:
                seen.remove(n)
            else:
                seen.add(n)
            if m in seen:
                seen.remove(m)
            else:
                seen.add(m)
        if nums[mid] in seen:
            seen.remove(nums[mid])
            # The last element in seen is the single one encounter only once
            return seen.pop()
        else:
            return nums[mid]

class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        # Implemented after reading comments from AI
        # - a ^ a = 0
        # - a ^ 0 = a
        # - XOR is commutative and associative
        single = 0
        for n in nums:
            single ^= n
        return single

@pytest.mark.parametrize(
    ("nums", "single_n"),
    [
        ([1], 1),
        ([2,2,1], 1),
        ([4,1,2,1,2], 4),
        ([1,2,3,1,2], 3)
    ]
)
def test_singleNumber(nums, single_n):
    assert Solution().singleNumber(nums) == single_n

Code¶

import pytest


class Solution:
    def singleNumber(self, nums: list[int]) -> int:
        # XOR cancels duplicate values and leaves the single one.
        acc = 0
        for n in nums:
            acc ^= n
        return acc


@pytest.mark.parametrize(
    ("nums", "expected"),
    [
        ([1], 1),
        ([2, 2, 1], 1),
        ([4, 1, 2, 1, 2], 4),
        ([1, 2, 3, 1, 2], 3),
        ([0, 0, -1], -1),
        ([-3, 7, 7, -3, 9], 9),
        ([10, 5, 10], 5),
    ],
)
def test_single_number(nums, expected):
    assert Solution().singleNumber(nums) == expected


# Interactive examples
Solution().singleNumber([2, 2, 1])
Solution().singleNumber([4, 1, 2, 1, 2])
Solution().singleNumber([1])