Single Number III — XOR Partition Trick That Splits Two Unique Elements

Problem Statement#

Given an integer array nums, in which 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. The algorithm must run in linear runtime complexity and use only constant extra space.

Constraints:

• 2 <= nums.length <= 3 * 10^4
• -2^31 <= nums[i] <= 2^31 - 1
• Each integer in nums will appear twice, only two integers will appear once.

Example 1:

Input:  nums = [1, 2, 1, 3, 2, 5]
Output: [3, 5]

Example 2:

Input:  nums = [-1, 0]
Output: [-1, 0]

Example 3:

Input:  nums = [0, 1]
Output: [1, 0]

Why This Problem Matters#

Single Number III is the natural escalation question after Single Number (LC 136) and Single Number II (LC 137). Once a candidate demonstrates the a ^ a = 0 cancellation trick, the FAANG interviewer pivots: what if two unique elements remain after cancellation? Now plain XOR of the array no longer isolates a single answer. You get a ^ b, the XOR of the two uniques mixed together, and you must derive a way to pull them apart with O(1) memory.

This problem is iconic because it forces you to discover a subtle property of XOR: any bit set in a ^ b must be set in exactly one of a and b. That observation is the foundation for the partition by bit technique used in dozens of harder problems including masked tries, k-th smallest subset XOR, and competitive programming staples on differing bits.

Companies like Google, Amazon, Meta, and Bloomberg use this question to separate candidates who memorize XOR tricks from those who genuinely understand bitwise algebra.

The Core Insight#

The trick is a two-pass XOR with a clever partition step.

Step 1 — Aggregate XOR. XOR every element of the array. All duplicates cancel, leaving xor_all = a ^ b where a and b are the two unique elements.

Step 2 — Find a differing bit. Since a != b, the value xor_all is non-zero, meaning at least one bit position differs between a and b. We isolate the lowest set bit using the classic trick diff_bit = xor_all & (-xor_all). This works because two's complement negation flips bits and adds one, so -x has the lowest set bit of x aligned with all higher bits inverted. AND-ing them keeps exactly that lowest set bit.

Step 3 — Partition and XOR each group. Walk the array a second time. Numbers that have diff_bit set go into group A, those that don't go into group B. Within each group, every duplicate still cancels via XOR, while a lives in one group and b in the other. After XOR-ing both groups separately, you have isolated a and b.

Visual Dry Run#

Input: nums = [1, 2, 1, 3, 2, 5]

Step 1. XOR everything:

1 ^ 2 ^ 1 ^ 3 ^ 2 ^ 5
= (1 ^ 1) ^ (2 ^ 2) ^ 3 ^ 5
= 0 ^ 0 ^ 3 ^ 5
= 3 ^ 5
3 = 011
5 = 101
xor_all = 110 (= 6)

Step 2. Lowest set bit of 6:

xor_all  = 0110
-xor_all = 1010 (two's complement)
xor_all & -xor_all = 0010
diff_bit = 2 (bit position 1)

Step 3. Partition by bit 1:

• Group A (bit 1 set): 2, 3, 2 → XOR = 2 ^ 2 ^ 3 = 3
• Group B (bit 1 clear): 1, 1, 5 → XOR = 1 ^ 1 ^ 5 = 5

Answer: [3, 5]. The algorithm correctly separated the two uniques without any extra memory.

Solution (Optimal)#

Python#

class Solution:
    def singleNumber(self, nums: list[int]) -> list[int]:
        # Step 1: XOR all numbers; pairs cancel, leaving a ^ b
        xor_all = 0
        for n in nums:
            xor_all ^= n
 
        # Step 2: isolate any differing bit (lowest set bit of a ^ b)
        diff_bit = xor_all & -xor_all
 
        # Step 3: partition by that bit and XOR each group separately
        a, b = 0, 0
        for n in nums:
            if n & diff_bit:
                a ^= n   # group with bit set
            else:
                b ^= n   # group with bit clear
        return [a, b]

JavaScript#

var singleNumber = function(nums) {
    // Step 1: XOR every element; duplicates cancel, leaving a ^ b
    let xorAll = 0;
    for (const n of nums) xorAll ^= n;
 
    // Step 2: lowest set bit of xorAll using two's complement trick
    const diffBit = xorAll & -xorAll;
 
    // Step 3: split into two groups by that bit and XOR each separately
    let a = 0, b = 0;
    for (const n of nums) {
        if (n & diffBit) a ^= n;
        else b ^= n;
    }
    return [a, b];
};

Complexity: Time O(n), Space O(1). Two linear passes, only a few integer accumulators.

Common Mistakes#

1. Using any non-zero bit instead of an isolated single bit. Some candidates write diff_bit = xor_all and try to partition on "any bit of xor_all". That fails because numbers may match xor_all partially. You must isolate exactly one bit.

2. Forgetting that xor_all is guaranteed non-zero. Since the two uniques differ, a ^ b cannot be zero. Defensive checks for xor_all == 0 signal you did not internalize the invariant.

3. Using xor_all & (xor_all - 1) instead of xor_all & -xor_all. The first clears the lowest bit (Brian Kernighan trick); the second isolates it. Mixing them up is a classic slip.

4. Mishandling negative numbers in fixed-width languages. In Java or C++ with signed 32-bit int, -INT_MIN overflows. The correct idiom uses unsigned semantics or the equivalent xor_all & (~xor_all + 1) form.

5. Returning order-dependent answers when the problem allows any order. Not a bug, but candidates sometimes waste time sorting unnecessarily.

Interview Tips#

• Verbalize the cancellation invariant first: "XOR all the numbers, duplicates cancel, leaving a ^ b." This signals you understand XOR algebra.
• When you reach the partition step, explicitly say "I need to find any bit where a and b differ" before writing code. This shows reasoning rather than rote memorization.
• Mention the two's complement trick x & -x and why it works. Senior interviewers love this detail.
• Discuss the alternative of finding the highest set bit and explain why isolating the lowest bit is typically faster.

Follow-up Questions#

Q: What if three numbers appear once? XOR alone cannot recover three numbers; the partition trick degenerates. Use a hash map or generalize via Gauss elimination on bit vectors.

Q: Generalize to k unique numbers with rest appearing twice. Solvable with a Walsh-Hadamard or recursive bit partition for very small k, but in general becomes a linear-algebra problem over GF(2).

Q: What if duplicates appear three times instead of twice? Combine Single Number II's mod-3 counting with the bit-partition trick from this problem to peel off two unique elements when the rest appear three times.

Q: Why does x & -x extract the lowest set bit? In two's complement, -x = ~x + 1. Adding one to the inverted bits propagates carries up through trailing zeros and stops at the original lowest set bit, leaving it set in -x while all lower bits are zero. AND-ing keeps only that bit.

Key Takeaways#

• XOR all elements to collapse duplicates and produce a ^ b.
• Isolate any differing bit between a and b using x & -x, the canonical "lowest set bit" idiom.
• Partition the array by that bit; each group has exactly one unique element while the rest cancel via XOR.
• Two linear passes, O(1) memory — meets the strict constant-space constraint.
• The pattern of XOR-then-partition is reusable in advanced problems involving differing bits across pairs or sets.
• Watch for two's complement edge cases in fixed-width languages; Python and JavaScript handle the trick cleanly.