LeetCode 136 · Bit Manipulation

Single Number, explained with a picture

Pairs of socks cancel; the odd one stays.

EasyBit Manipulation
▶ Watch it step by step

The problem

Every number in the list appears twice except one. Find that single number using constant extra space.

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

Picture it

Picture socks: every sock has a twin except one. XOR (^) works like a light switch: flipping it twice puts it back. If we XOR all the numbers together, every pair switches its lights on and then off again, leaving only the lonely sock’s lights on.

How to recognise it

  • Every value appears exactly twice except one, and you must find the odd one out.
  • The problem asks for O(1) extra space, which rules out a dictionary or set of counts.
  • "Pairs cancel" is the hint for XOR (^, exclusive or): x ^ x == 0, x ^ 0 == x, and the order of the operations does not matter.
  • Up to 3 × 10^4 numbers, between −3 × 10^4 and 3 × 10^4.

Start with brute force

For each number, count how often it appears; return the one that appears once.

def single_brute(nums):
    for x in nums:
        if nums.count(x) == 1:
            return x

Each count scans the whole list, so this is O(n²) time and O(1) space. With n = 3 × 10^4 that can reach about 9 × 10^8 comparisons, far too slow in Python. A dictionary of counts fixes the time (O(n)) but uses O(n) extra space, which the problem forbids.

From brute force to the idea

  1. Find the waste. We do not need the counts themselves, only whether each count is odd or even.
  2. Think of each bit as a switch. XOR with a number flips the switches where that number has a 1 bit. Flipping a switch twice puts it back.
  3. Fold everything together. Start with acc = 0 and XOR in every number. Because XOR is commutative and associative, the result is the same as if equal numbers were next to each other: each pair gives 0, and 0 changes nothing.
  4. What remains is the single. After all pairs cancel, acc holds exactly the number that appeared once.

This is the key idea: XOR of all the numbers cancels every pair and leaves the single one, using one variable.

For example, 4 ^ 1 ^ 2 ^ 1 ^ 2 = 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.

The key idea

a ^ a = 0 and a ^ 0 = a, so XOR of everything is the single number. O(n), O(1).

Python solution

def single_number(nums):
    acc = 0
    for x in nums:
        acc ^= x                  # a pair flips a switch twice: back off
    return acc

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute force (count each)O(n²): a full scan per numberO(1)
Dictionary of countsO(n): one passO(n): one entry per distinct value
XOR fold (shown code)O(n): one XOR per numberO(1): a single accumulator

Edge cases

  • One number only ([7]): returns 7.
  • The single number is 0 ([0, 4, 4]): returns 0, correctly.
  • Negative numbers ([-1, -1, 5] or [2, 2, -3]): work, because Python's XOR on negative integers behaves like two's complement with unlimited width; pairs still cancel.
  • The promise is broken (some value appears three times): the answer is wrong. [1, 1, 1, 3, 3, 7] returns 6 (1 ^ 7), not 7. XOR only tracks odd versus even counts.
  • Empty list: returns 0, which is not a real answer; LeetCode guarantees at least one number.

Common mistakes

  • Starting acc at the first number and then XOR-ing the whole list again, which cancels that number.
  • Using + and - to cancel pairs: you cannot know whether to add or subtract a value without remembering it.
  • Sorting first to compare neighbours: correct, but O(n log n) and it changes or copies the list.
  • Expecting XOR to work when values appear three times each.
Your turn: two single numbers

Now every number appears twice except two different ones (LeetCode 260). Return both, in any order. For [1, 2, 1, 3, 2, 5] the answer is 3 and 5. Use O(1) extra space. Describe your approach, then write it if you like.

Compare with our answer

XOR of everything gives x ^ y, the two singles combined. It is not 0 (they differ), so pick any 1 bit in it: xy & -xy keeps the lowest one. That bit is 1 in one single and 0 in the other, so it splits all numbers into two groups, each with one single and only whole pairs. XOR each group.

def single_two(nums):
    xy = 0
    for x in nums:
        xy ^= x                     # x ^ y, the two singles
    low = xy & -xy                  # a bit where x and y differ
    a = 0
    for x in nums:
        if x & low:
            a ^= x
    return [a, xy ^ a]

Time O(n), space O(1). It works for negative numbers in Python too.

A strong answer mentions: why x ^ y is not zero, choosing a bit where they differ, and that pairs always land in the same group.

Check what stuck

1. A log lists every opened file once and every closed file once; exactly one file is still open. Each file opens at most once. Which approach fits best?

2. Why does the order of the numbers not matter to the XOR fold?

3. For which input does the shown code return a wrong answer?

Score 60% or more and the lesson is marked complete.