Single Number (LeetCode 136)

The problem

You get a non-empty array of integers. Every value appears exactly twice, except one value that appears once. Return that value. The follow-up asks for O(n) time and O(1) extra space.

Input:  [4, 1, 2, 1, 2]
Output: 4

1 and 2 each appear twice; 4 appears once.

How to think about it

Start with brute force. For each element, count how many times it appears by scanning the array: O(n²). A hash map of counts fixes the time to O(n), but uses O(n) space. Sorting and checking neighbours is O(n log n). None of these meets O(n) time with O(1) space.

The key insight: XOR cancels pairs. Three facts about XOR do all the work:

• x ^ x = 0 (a number cancels itself),
• x ^ 0 = x (zero changes nothing),
• XOR is commutative and associative, so order does not matter.

So XOR-ing the whole array is the same as grouping each pair together: every pair becomes 0, and what is left is 0 ^ single = single. One pass, one variable.

Why it works bit by bit. Look at any single bit position. Each paired number contributes its bit twice, which cancels. Only the single number’s bit survives. XOR is “addition mod 2” per bit.

Which pattern is this? Bit manipulation, XOR cancellation. The tell is “every element appears twice except one”, especially with an O(1) space demand.

Approach

1. Set r = 0.
2. For every x in the array, do r ^= x.
3. Return r.

Solution

def single_number(nums):
    r = 0
    for x in nums:
        r ^= x          # pairs cancel: x ^ x = 0
    return r
# single_number([4,1,2,1,2]) -> 4

Dry run

On [4, 1, 2, 1, 2], with r shown in binary:

The 1s and 2s switch their bits on and then off again. The answer is 4.

Complexity

• Time: O(n). One pass, one XOR per element.
• Space: O(1). Only the running value r.

Edge cases and pitfalls

• Single-element array ([1]) returns that element.
• Negative numbers work in Python: XOR uses two’s-complement bits on unbounded ints, so [-3, 5, 5] returns -3.
• Starting r at the first element instead of 0 works too, but 0 is cleaner and handles every length.
• If an element can appear three times, XOR fails. That is Single Number II.

Related problems

• Single Number II (LeetCode 137): every other number appears three times.
• Single Number III (LeetCode 260): two numbers appear once; XOR, then split.
• Missing Number (LeetCode 268): the same cancellation, between indices and values.