Single Number III: Finding Two Unique Numbers with XOR

LeetCode Single Number III (Problem 260) asks: given an integer array nums where exactly two elements appear only once and all the other elements appear exactly twice, find the two elements that appear only once. You can return the answer in any order.

Problem description

You are given an array of integers. Every number appears exactly twice, except for two numbers that each appear exactly once. Find those two unique numbers in O(n) time and O(1) space.

Examples:

• [1, 2, 1, 3, 2, 5] returns [3, 5]
• [0, 1] returns [0, 1]
• [-1, 0] returns [-1, 0]

The key insight

If there were only one unique number, you could XOR everything together and the pairs would cancel. But here there are two unique numbers. XOR-ing the entire array gives you a ^ b, where a and b are the two unique numbers. That is useful, but it is not the answer itself.

The trick is to split the array into two groups so that a ends up in one group and b ends up in the other. If you can do that, you can XOR each group separately and each group will produce one of the unique numbers.

How do you split them? Since a and b are different, their XOR (a ^ b) has at least one bit set to 1. That set bit is a position where a and b differ. You can use any set bit in a ^ b to partition the entire array: numbers with that bit set go in one group, numbers with that bit unset go in the other.

Every paired number ends up in the same group as its twin (since identical numbers have the same bits). And a and b are guaranteed to land in different groups because they differ at that bit. So each group contains exactly one unique number plus some pairs that cancel under XOR.

The solution

def single_number(nums):
    xor = 0
    for num in nums:
        xor ^= num
    diff = xor & (-xor)
    a = 0
    for num in nums:
        if num & diff:
            a ^= num
    return [a, xor ^ a]

Step-by-step walkthrough

Let's trace through [1, 2, 1, 3, 2, 5] step by step. The two unique numbers are 3 and 5.

The second unique number does not need its own loop. Once you know a, you get b for free: b = xor ^ a. Since xor = a ^ b, XOR-ing it with a cancels a and leaves b.

Complexity analysis

The algorithm makes two passes through the array: one to compute the total XOR and one to partition and XOR the first group. Both passes are O(n). The only extra variables are xor, diff, and a, so space is O(1).

Building blocks

This problem decomposes into two reusable building blocks that CodeBricks drills independently.

XOR cancellation (accumulate XOR across a collection)

Initialize a result to 0 and XOR every element into it. Pairs cancel to 0 and only unpaired values survive. This is the same pattern from Single Number (LeetCode 136), and it forms the foundation of the first pass here.

xor = 0
for num in nums:
    xor ^= num

Bit partitioning (split by a distinguishing bit)

Once you have the XOR of two unknown values, isolate a set bit and use it to divide the collection into two groups. Each group contains exactly one of the unknowns plus pairs that cancel. This partition-and-cancel technique is specific to problems with exactly two unique elements.

diff = xor & (-xor)
a = 0
for num in nums:
    if num & diff:
        a ^= num

The key insight is that the rightmost set bit of a ^ b tells you a position where the two unknowns differ. Any set bit would work, but the rightmost one is the easiest to isolate.

Edge cases

Two-element array. If nums has exactly two elements, both are unique. The XOR of the array is a ^ b, and the partitioning still works correctly. One element goes in each group.

One of the unique numbers is 0. XOR with 0 is the identity operation, so a ^ b just equals the other unique number. The partitioning bit comes from the nonzero unique number, and the group containing 0 will XOR down to 0 correctly.

Negative numbers. The x & (-x) trick works on negative numbers in two's complement. The XOR and AND operations are bitwise and do not care about sign. The algorithm handles negative values without any special cases.

All bits differ. If a and b differ in every bit position, a ^ b has many set bits. The algorithm only needs one of them. Using x & (-x) picks the rightmost one automatically.

From understanding to recall

The two-pass XOR approach is elegant, but it has a few moving parts: computing the total XOR, isolating a distinguishing bit, partitioning, and recovering the second number. Under interview pressure, it is easy to forget the order of operations or mix up which variable holds what.

Spaced repetition turns this multi-step pattern into muscle memory. You write the solution from scratch, verify each piece, and then do it again at increasing intervals. After a few rounds, the bit partitioning trick stops feeling clever and starts feeling obvious. That is when you own the pattern.

Related posts

• Single Number - The simpler version where only one element appears once. Pure XOR cancellation in a single pass.
• Single Number II - Every element appears three times except one. Requires bit counting modulo 3 or a ones/twos state machine.
• Number of 1 Bits - Count set bits using n & (n - 1). A complementary bit manipulation technique that builds the same low-level intuition.