Introduction

The phrase “find the single number” usually refers to a specific interview-style problem: every value in the list appears twice except one value that appears once. In that case, the best solution is usually the XOR trick, because it runs in linear time and constant extra space.

Understand the Exact Problem

Before choosing an algorithm, pin down the rule. There are several similar problems:

• find whether a specific value exists
• find the first unique value
• find the one value that appears once when every other value appears twice

This article focuses on the third case, since that is the classic “single number” formulation.

Given this list:

numbers = [4, 1, 2, 1, 2]

The answer is 4, because every other number is duplicated.

The XOR Solution

XOR has a useful property for this problem:

• 'x ^ x becomes 0'
• 'x ^ 0 becomes x'
• XOR is associative and commutative

That means all duplicate pairs cancel out, leaving only the value that appears once.

1def single_number(numbers: list[int]) -> int:
2    result = 0
3    for value in numbers:
4        result ^= value
5    return result
6
7
8print(single_number([4, 1, 2, 1, 2]))
9print(single_number([7, 3, 5, 3, 5]))

This runs in O(n) time with O(1) extra space, which is why it is the standard answer.

Why XOR Works

Take the list [4, 1, 2, 1, 2]:

0 ^ 4 ^ 1 ^ 2 ^ 1 ^ 2

Reorder conceptually:

0 ^ 4 ^ (1 ^ 1) ^ (2 ^ 2)

Duplicate pairs become zero:

0 ^ 4 ^ 0 ^ 0

The result is 4.

This only works cleanly when the problem guarantees that all non-unique values appear exactly twice. If the input rule changes, the algorithm must change too.

Use a Frequency Map When the Rules Differ

If the list can contain arbitrary repetition counts, use a counting dictionary instead. It is slightly less memory-efficient, but it handles more general inputs.

1from collections import Counter
2
3
4def first_value_with_count_one(numbers: list[int]) -> int | None:
5    counts = Counter(numbers)
6    for value in numbers:
7        if counts[value] == 1:
8            return value
9    return None
10
11
12print(first_value_with_count_one([9, 4, 9, 2, 4, 7]))

This approach is also better if you need the first unique item while preserving the original list order.

Sorting Is Possible but Usually Not Best

Another solution is to sort the list and compare neighbors:

1def single_number_sorted(numbers: list[int]) -> int:
2    values = sorted(numbers)
3    i = 0
4
5    while i < len(values) - 1:
6        if values[i] != values[i + 1]:
7            return values[i]
8        i += 2
9
10    return values[-1]
11
12
13print(single_number_sorted([4, 1, 2, 1, 2]))

This is valid, but sorting costs O(n log n) time and often does more work than necessary. Use it only if the data is already sorted or if you need sorted output for another reason.

Choosing the Right Method

Use XOR when:

• exactly one number appears once
• every other number appears exactly twice
• the values are integers

Use counting when:

• repetition counts vary
• you need the first unique value in original order
• the input may violate the strict XOR assumptions

That distinction matters more than micro-optimizing syntax.

Common Pitfalls

The biggest mistake is using XOR on the wrong problem. If one value appears three times, or several values are unique, XOR will not produce the answer you expect.

Another issue is forgetting that XOR is an integer operation. If the list contains strings, floats, or complex objects, use a counting structure instead.

Sorting-based solutions also often mutate the original list by accident. If the original order matters elsewhere, sort a copy rather than the list itself.

Finally, watch the return contract. Some problems guarantee a valid answer, while real application code may need to return None or raise an exception when no unique value exists.

Summary

• The classic single-number problem is best solved with XOR.
• XOR gives O(n) time and O(1) extra space.
• The method only works when every duplicate appears exactly twice.
• Use Counter or a dictionary when the input rules are more general.
• Define the problem precisely before choosing the algorithm.