medium Single Number III

Single Number III

Third turn of the screw. In Single Number one value was unpaired; in Single Number II the duplicates came in threes. Here we are back to duplicates in pairs, but two values appear exactly once instead of one: every value appears exactly twice, except two values that each appear once. Return those two (order doesn't matter), in O(n) time and O(1) space. Example: [1, 2, 1, 3, 2, 5] → [3, 5].

A single XOR fold got us the loner last time. Fold this array and you don't get an answer — you get a ^ b, the two loners smeared together (every doubled value still cancels). That is not nothing: it is half the solution, and the other half is a trick you already have — x & -x to isolate one bit. This page is where XOR cancellation and lowest-set-bit isolation click together.

Naive baseline & its cost

A hash map from value → count, then return the two keys whose count is 1: O(n) time, O(n) space. Correct, obvious, and exactly what you'd ship. The whole exercise is keeping the O(n) time while crushing space to O(1) — and doing it without knowing the two answers up front.

The insight, in two moves

Move 1 — fold to a ^ b. XOR the entire array into one accumulator. Every value that appears twice contributes v ^ v = 0 and vanishes; the two loners a and b each appear once and survive. What's left is exactly xorAll = a ^ b. We can't read a and b out of their XOR directly — but this combined value is a map of where they differ: recall a XOR is 1 in exactly the bit positions where its two operands disagree.

Move 2 — find one bit where they differ, and use it to separate them. The two loners are distinct (a ≠ b), so xorAll ≠ 0: it has at least one set bit, and every set bit marks a position where a and b have opposite values. Pick any one such bit. The cleanest choice is the lowest set bit, isolated with the two's-complement identity from the tricks page:

diff = xorAll & -xorAll     // keeps only the lowest set bit of xorAll

Why x & -x isolates the lowest set bit (the proof, compact): -x = ~x + 1. Below the lowest set bit, x is all zeros, so ~x is all ones there; the +1 ripples through those ones, flipping them back to zero and carrying into the lowest-set-bit position, which becomes 1. Every bit above is ~x's inversion, untouched by the carry — so it is the opposite of x there. AND-ing x with -x keeps only the one position where both are 1: the lowest set bit. Nothing else survives.

Why splitting on that bit finishes the job

Partition the array into two groups: numbers with diff's bit set, and numbers without it. Two facts make this a clean win:

• The two loners land in different groups. At the diff bit, a and b disagree (that's why the bit is set in a ^ b) — so exactly one of them has the bit, the other doesn't. They are separated.
• Every doubled value stays whole inside one group. A value's two identical copies have identical bits, so they test the same on the diff bit and fall in the same group — where they XOR to 0 and disappear.

So within each group, all the pairs cancel and exactly one loner remains. XOR-fold each group and you read off a and b separately. In code you only need to fold one group to get a; the other is free, because b = xorAll ^ a (we already know a ^ b).

Traced worked example — [1, 2, 1, 3, 2, 5]

Pass 1 — XOR everything into xorAll (3-bit binary; start at 0):

xorAll = 110₂ = 6 = 3 ^ 5. The two 1s and two 2s cancelled along the way; only 3 ^ 5 is left.

Isolate the low bit: diff = 6 & -6. In bits, 6 = 110 and -6 = …11111010, so 110 & …010 = 010₂ = 2 — bit 1.

Pass 2 — partition on bit 1 (x & 2) and fold the group where the bit is set:

The bit-set group is {2, 3, 2}; its two 2s cancel, leaving a = 3. Then b = xorAll ^ a = 6 ^ 3 = 5. (Sanity check: the other group {1, 1, 5} XORs to 1 ^ 1 ^ 5 = 5 — same b, confirming the shortcut.) Answer [3, 5].

Java: XOR fold, isolate, split

class Solution {
    public int[] singleNumber(int[] nums) {
        int xorAll = 0;
        for (int x : nums) xorAll ^= x;   // pass 1: collapses to a ^ b

        int diff = xorAll & -xorAll;      // lowest set bit: a and b differ here

        int a = 0;
        for (int x : nums) {
            if ((x & diff) != 0) a ^= x;  // pass 2: fold only the bit-set group
        }
        int b = xorAll ^ a;               // the other loner falls out for free
        return new int[]{a, b};
    }
}

Go: XOR fold, isolate, split

package main

import "fmt"

func singleNumber(nums []int) []int {
    xorAll := 0
    for _, x := range nums {
        xorAll ^= x // pass 1: collapses to a ^ b
    }

    diff := xorAll & -xorAll // lowest set bit: a and b differ here

    a := 0
    for _, x := range nums {
        if x&diff != 0 {
            a ^= x // pass 2: fold only the bit-set group
        }
    }
    b := xorAll ^ a // the other loner falls out for free
    return []int{a, b}
}

func main() {
    fmt.Println(singleNumber([]int{1, 2, 1, 3, 2, 5})) // [3 5]
}

Complexity — derived from the code

Two passes over n elements, each iteration a couple of O(1) bit ops; the diff computation is O(1). Total time = O(n) (two linear passes, no nesting). We hold four ints (xorAll, diff, a, b) regardless of input size, so space = O(1). That matches the hash map on time and beats it on space (O(1) vs O(n)), and beats a sort (O(n log n)).

Judgment layer — when this trick, and when the hash map

• Reach for the XOR + x & -x split when the structure is exactly "all values twice except two" and O(1) space is demanded. It is the canonical staff-signal answer: it shows you can chain XOR cancellation with lowest-set-bit isolation, the two ideas the whole module has been building toward.
• Prefer the hash map / frequency count when the constraints are fuzzier or likely to shift: more than two loners, or values that repeat a variable number of times, or you must also report the counts, or the inputs aren't XOR-able integers. The map handles every variant with a trivial edit; this trick handles none of them — it is exquisitely tuned to the "twice-except-two" promise and breaks the instant that promise weakens. In an interview, state the map baseline first ("O(n) space, obviously correct"), then offer this as the O(1)-space refinement and explain why the split works — that reasoning is the actual signal.
• The trade you are making: the bit approach buys O(1) space and elegance at the cost of being brittle and needing a careful correctness argument; the hash map costs O(n) space but is general, readable, and robust. Match the tool to how firm the "twice-except-two" guarantee really is.
• vs. plain single-XOR (Single Number I): one fold isn't enough here — it only yields a ^ b. Recognizing that the fold is a starting point, not the answer, and that a differing bit re-splits the problem into two independent Single-Number-I subproblems, is exactly what this problem tests.

Edge cases & traps

• xorAll can never be 0. The two loners are distinct, so a ^ b ≠ 0 and diff always isolates a real bit. If the problem allowed the two uniques to be equal, the split would have no bit to key on — but then they'd be a pair, contradicting the premise.
• Any differing bit works; lowest is just convenient. x & -x picks the lowest set bit, but partitioning on any set bit of xorAll separates a and b correctly. The lowest is chosen only because it is a one-liner to isolate.
• Negative numbers are fine. XOR and x & -x operate on the raw two's-complement bits, so negative loners split and reconstruct correctly — the group membership test x & diff only inspects a single bit and never cares what the value "means". The one pedantic corner is xorAll == Integer.MIN_VALUE (bit 31 alone set): -xorAll overflows back to itself, but x & -x then equals x, which is that single set bit — so it still isolates correctly.
• Return order is immaterial. Which loner is called a depends on which one carries the diff bit; the problem accepts the pair in either order.
• Don't fold the wrong group into b. Using b = xorAll ^ a is the clean move; if you instead fold the second group explicitly, make sure you test (x & diff) == 0, not a re-use of the first condition.

Takeaways

• Fold the array → xorAll = a ^ b: the doubles cancel, the two loners smear together.
• xorAll marks every bit where the loners differ; diff = xorAll & -xorAll grabs one such bit (the lowest).
• Splitting on that bit sends a and b to different groups while keeping each pair intact, turning the problem into two independent Single-Number-I folds — and b = xorAll ^ a saves the second fold.
• O(n) time, O(1) space. Reach for it only when "twice-except-two" is guaranteed and O(1) space matters; otherwise the hash map is the more robust engineering call.

Authored from the XOR-cancellation and two's-complement x & -x proofs; both samples compiled and hand-traced on [1,2,1,3,2,5] → [3,5] (xorAll=6, diff=2, groups {2,3,2}→3 and {1,1,5}→5).