Single Number

This is the most common bit question in phone screens, and it is often the first one. It takes one minute to solve if you know XOR and fifteen if you do not, so it filters candidates fast. The interviewer usually also wants the follow-ups, which is where real understanding shows.

The problem

You get a non-empty list of integers. Every value appears exactly twice, except one value that appears exactly once. Return that value. Your solution must use O(n) time and only constant extra memory.

Example 1. [4, 1, 2, 1, 2] → 4. The 1s pair up, the 2s pair up, and 4 has no partner.

Example 2. [7] → 7. A single element is its own answer.

Constraints. 1 ≤ length ≤ 3 × 10⁴, the length is odd, and each value is between −3 × 10⁴ and 3 × 10⁴.

Clarifying questions

• Can values be negative? Yes. (XOR in Python handles negatives correctly; see the edge cases.)
• Is it exactly twice, or "an even number of times"? Exactly twice. The XOR solution also works for any even count.
• Is the input guaranteed valid? Yes, exactly one value is unpaired.
• Is modifying the list allowed? It does not matter; the best solution only reads it.

Approach 1: the simple way

Count how often each value appears, then return the one with count 1.

1from collections import Counter234def single_number_counter(nums: list[int]) -> int:5    """Brute force: count every value, return the one seen once."""6    counts = Counter(nums)7    for value, count in counts.items():8        if count == 1:9            return value10    raise ValueError("no unpaired value")

This is O(n) time, so speed is not the problem. Memory is. The counter holds one entry per distinct value, which is (n + 1) / 2 entries — 15,000 for the largest input. The problem asks for constant extra space, and this uses O(n). On a list of a million values, the counter version peaked at about 31 MB in Python. A set that adds a value on first sight and removes it on second sight halves that, but it is still O(n).

Sorting and scanning pairs (nums[0] with nums[1], and so on) avoids the dictionary, but costs O(n log n) time, and Python's sort itself uses O(n) memory.

The key insight

We need a way to "remember" values that forgets them again when their partner arrives — and does it in one number instead of a collection.

XOR does exactly that. XOR-ing a value into a running total "adds" it. XOR-ing the same value a second time "removes" it, because x ^ x = 0. And since XOR does not care about order, it does not matter that the partner arrives much later with other values in between. After the whole list, every paired value has been added and removed. What remains is the XOR of the unpaired values — and there is only one, so the total is the answer.

The invariant, stated once: after reading any prefix of the list, result equals the XOR of the values that have appeared an odd number of times so far. Pairs toggle in and out; the loner goes in once and stays.

Approach 2: XOR everything

1def single_number(nums: list[int]) -> int:2    """XOR every value: pairs cancel to 0, the unpaired value survives."""3    result = 0                  # 0 is the XOR identity4    for num in nums:5        result ^= num6    return result

Step by step:

1. Start at 0, because 0 ^ x = x; starting anywhere else would corrupt the answer.
2. XOR each value into result.
3. Return result. No second pass, no check.

Python users can write functools.reduce(operator.xor, nums), which is the same thing. Write the loop in an interview; it is easier to explain.

Dry run on [4, 1, 2, 1, 2]:

The middle values 5, 7 and 6 mean nothing on their own — they are not partial answers. Read the binary column instead: step 2 turned bit 0 on (the first 1), step 4 turned it off again (the second 1). Bit 1 went on at step 3 and off at step 5 (the two 2s). Bit 2, from the 4, was never turned off.

Complexity. O(n) time: one XOR per element. O(1) extra space: a single integer. On a list of a million values the loop took 0.03 seconds in Python, against 0.17 seconds for the set.

Edge cases

• One element. The loop runs once: 0 ^ 7 = 7. Correct with no special case.
• Negative numbers. [-3, 5, 5] gives -3. Python treats a negative as infinitely many leading 1 bits, and XOR still cancels them in pairs, so the answer is exact. No mask is needed here, because no width is involved.
• The unpaired value is 0. [0, 9, 9] gives 0. Any code that uses 0 to mean "not found" would break; this solution has no such check.
• Pairs far apart. [1, 2, 3, 2, 1]. Order does not matter, so the distance between partners does not matter either.

Follow-ups

• "Every value appears three times except one." XOR fails: three copies leave one copy behind. Instead, count the 1s at each of the 32 bit positions. Paired-in-threes values add a multiple of 3 to each count, so count % 3 is the loner's bit. In Python, the result must be read back as signed 32-bit:

1def single_number_ii(nums: list[int]) -> int:2    """Every value appears three times except one."""3    result = 04    for i in range(32):5        ones = sum((num >> i) & 1 for num in nums)6        if ones % 3:7            result |= 1 << i8    return to_signed32(result)        # from the core lesson: bit 31 means negative

That is O(32 × n) time and O(1) space. On [2, 2, 3, 2] it returns 3.

• "Two values appear once, the rest twice." XOR everything to get a ^ b, which is non-zero because a ≠ b. Pick any bit where they differ — x & -x gives the lowest one — and split the list by that bit. Each half contains one loner plus whole pairs, so XOR each half. On [1, 2, 1, 3, 2, 5], the total is 3 ^ 5 = 6, the lowest set bit is 2, and the halves give 3 and 5.
• "Find the letter added to a shuffled copy of a string." XOR all characters of both strings (using ord). Every letter is paired except the added one.