medium Single Number II

Single Number II

Same shape as Single Number, one number changed: now every value appears exactly three times, except one value that appears once. Find the loner, in O(n) time and O(1) space. Example: [3, 3, 3, 5] → 5.

The plain XOR fold is dead here, and it's worth saying why: XOR's magic was that v ^ v = 0 — pairs cancel. But three copies XOR to v ^ v ^ v = 0 ^ v = v. Three copies do not cancel; they leave one copy behind. Fold the whole array and you get the loner XORed with one copy of every tripled value — noise, not the answer. We need a counter that resets every third time, not every second. Two ways to build one.

Naive baseline & its cost

A hash map from value → count, then return the key whose count is 1: O(n) time, O(n) space. Perfectly correct, and it's what you'd write in production. The exercise is to keep the O(n) time but crush space to O(1).

Approach 1 — count each bit column mod 3 (the intuitive one)

The idea, from nothing. Forget the numbers as wholes; look at one bit position at a time, say bit 0, across the entire array. Every value that appears three times contributes its bit-0 value three times to that column. The loner contributes its bit-0 value once. So the total number of 1s in column 0 is 3×(something) + (loner's bit 0). Take that count mod 3 and the tripled contributions vanish (any multiple of 3 is 0 mod 3), leaving exactly the loner's bit for that column. Do this for all 32 bit positions and you have reconstructed the loner bit by bit.

Why it's airtight: addition of the per-number bit values is done independently per column, and (3k + b) mod 3 = b for b ∈ {0,1}. Every column recovers its true loner bit, so the assembled 32-bit word is exactly the loner. This generalizes for free: "appears m times except one" becomes count mod m.

Traced example (counting) — [3, 3, 3, 5]

3 = 011₂, 5 = 101₂. Tally each column, then reduce mod 3:

Assemble from the "loner's bit" column, high to low: bit2 bit1 bit0 = 1 0 1 = 101₂ = 5. The three 3s piled up to counts of 4, 3, 0 in the columns; mod 3 those tripled contributions dissolved, exposing 5. (Bit 1 shows why mod-3 — not "count == 1" — is required: its count is 3, which is not 1, yet it correctly reduces to 0.)

Java: count bits mod 3

class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {   // Java int is exactly 32 bits
            int sum = 0;
            for (int x : nums) {
                sum += (x >> i) & 1;    // bit i of x, 0 or 1
            }
            if (sum % 3 != 0) {
                result |= (1 << i);      // loner has this bit set
            }
        }
        return result;                   // bit 31 lands in the sign slot, so negatives reconstruct correctly
    }
}

Go: count bits mod 3

package main

import "fmt"

func singleNumber(nums []int) int {
    // Go's int is 64-bit here, so accumulate into an int32 to make bit 31
    // the sign bit exactly as Java's int does; otherwise a negative loner
    // would come back as a large positive (its low 32 bits).
    var result int32 = 0
    for i := 0; i < 32; i++ {
        sum := 0
        for _, x := range nums {
            sum += int((int32(x) >> uint(i)) & 1)
        }
        if sum%3 != 0 {
            result |= 1 << uint(i)
        }
    }
    return int(result)
}

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

Approach 2 — the ones/twos state machine (the classic trap)

The counting version does 32 passes conceptually. Can we do it in one pass with two registers? Yes — but this is the version people memorize wrong, so we derive it instead of reciting it.

Think of each bit position as a tiny counter that must cycle 0 → 1 → 2 → 0 as copies arrive, i.e. a mod-3 counter. Two bits of state can represent three values {0,1,2}. Track them across all positions at once with two ints:

• ones = the set of bit positions currently seen 1 time (mod 3),
• twos = the set of bit positions currently seen 2 times (mod 3).

A position is never in ones and twos simultaneously (a counter is in exactly one state), and being in neither means "seen 0 times mod 3". When a new number x arrives, each position it touches should advance one step. The update that implements the 0→1→2→0 cycle is:

ones = (ones ^ x) & ~twos;   // step positions into/out of "seen once"...
twos = (twos ^ x) & ~ones;   // ...then into/out of "seen twice", using the JUST-updated ones

Why this cycles correctly. Consider a single bit where x has a 1:

• State 0 (not in ones, not in twos): ones becomes (0^1)&~0 = 1; then twos becomes (0^1)&~1 = 0. Now in ones — state 1. ✓
• State 1 (in ones): ones becomes (1^1)&~0 = 0; then twos becomes (0^1)&~0 = 1. Now in twos — state 2. ✓
• State 2 (in twos): ones becomes (0^1)&~1 = 0; then twos becomes (1^1)&~0 = 0. Back to neither — state 0, the third copy erased. ✓

And where x has a 0 at that bit, both updates XOR with 0 and mask, leaving the state unchanged — exactly right, an absent bit shouldn't advance the counter. After the whole array, every tripled value's bits have cycled back to state 0; the loner's bits, seen once, sit in ones. Return ones.

The trap: the order matters. twos must use the already-updated ones. Swap the two lines, or compute both from the old values, and the third-copy reset breaks. This ordering is the single most common bug people reproduce from memory — derive it, don't recall it.

Traced example (state machine) — [3, 3, 3, 5]

All values in 3-bit binary; ~ shown only over the low 3 bits for readability (the high bits stay 0):

After the three 3s, both registers are back to 000 (the triple fully erased). The lone 5 lands in ones = 101₂ = 5. Return ones → 5. Same answer as the counting method, in one pass.

Java: ones/twos state machine

class Solution {
    public int singleNumber(int[] nums) {
        int ones = 0, twos = 0;
        for (int x : nums) {
            ones = (ones ^ x) & ~twos;   // order matters: update ones first...
            twos = (twos ^ x) & ~ones;   // ...then twos, using the new ones
        }
        return ones;                     // positions seen exactly once (mod 3)
    }
}

Go: ones/twos state machine

package main

import "fmt"

func singleNumber(nums []int) int {
    ones, twos := 0, 0
    for _, x := range nums {
        ones = (ones ^ x) &^ twos // &^ is Go's "AND NOT" (bit clear): ones & ~twos
        twos = (twos ^ x) &^ ones
    }
    return ones
}

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

Complexity — both approaches

• Counting mod 3: outer loop 32 (constant number of bit positions), inner loop n. Time = 32×n = O(32n) = O(n) with a 32× constant factor; space = O(1) (the accumulator).
• State machine: a single pass of n iterations, each doing a handful of O(1) bit ops. Time = O(n) with a tiny constant; space = O(1) (two ints). This is the tighter constant — one pass, no per-bit loop.

Both are O(n)/O(1). The state machine is faster in practice (no 32× factor) but harder to get right and to read; the counting method is slower by a constant but self-evidently correct and trivially generalizes to "appears k times."

Judgment layer — which to reach for

• In an interview, lead with counting mod 3. You can derive and defend it on the spot, it obviously generalizes ("for k copies, count mod k"), and it's hard to get wrong. State its O(32n) cost honestly.
• Offer the state machine as the optimization when asked to shave the constant or do it in one pass — but only if you can derive the update rule live. Reciting it from memory and fumbling the ones-before-twos ordering is worse than not offering it. Deriving it is a strong staff-level signal.
• vs. the hash map: if O(n) space is fine, the frequency map is the most readable and the most robust to changing constraints (counts, k copies, multiple loners) — the same judgment as in Single Number I. The bit tricks are the right call specifically when O(1) space is demanded.
• vs. plain XOR: do not reach for the single-XOR fold here — it only cancels pairs. Three copies survive as one copy, so the fold returns noise. Recognizing that XOR fails the moment copies aren't even-counted is the insight this problem is testing.

Edge cases & traps

• Negative loner & integer width. This is the sharp edge. In Java, int is exactly 32 bits, so looping i = 0..31 and setting result |= (1 << i) places bit 31 in the sign position — a negative loner reconstructs correctly. In Go, int is 64-bit on modern platforms; the naive 32-bit loop would return a negative loner as its low-32-bit positive image (e.g. -5 → 4294967291). The fix shown accumulates into an int32 so bit 31 is the sign bit, matching Java. The state machine has no such issue — it operates on the full native width uniformly.
• Ordering in the state machine. As proven above, twos must consume the freshly-updated ones. Reversing the lines silently breaks the third-copy reset.
• Overflow in the count. sum per column is at most n; for any realistic n it fits an int. No overflow concern here (unlike sum-based approaches to Missing Number).

Takeaways

• XOR cancels pairs, not triples — the moment copies aren't even-counted, you need a mod-k counter.
• Counting bits mod 3 is the derive-on-the-spot answer: O(32n)/O(1), generalizes to any k.
• The ones/twos state machine is the one-pass optimization — correct only if you keep the update order; derive it, never recite it.
• Mind integer width: Java's 32-bit int reconstructs negatives for free; Go's 64-bit int needs an int32 accumulator.

Both approaches derived from the mod-3 per-column argument; all four samples compiled and hand-traced on [3,3,3,5] → 5, with the negative-loner width trap verified separately ([3,3,3,-5] → -5).