XOR patterns

LC 136 (Single Number): an array where every value appears twice except one, return the lone value. Sample input [4, 1, 2, 1, 2], expected answer 4. The first reflex is a hash set: scan once, count, return the key with count 1. That works in O(n) time but O(n) space, and the prompt says O(1) space. The second reflex is to sort and scan adjacent pairs: O(n log n) time, O(1) space if you sort in place. Also rejected, because the prompt says O(n) time.

The accepted answer is one line. XOR every element into an accumulator, return the accumulator. It runs in O(n) time, O(1) space, and works on negatives, on INT_MIN, on a single-element array, on every pathological case the grader throws at it. There are no special cases. The reason is one identity: XOR is its own inverse — a ^ a = 0 and a ^ 0 = a — so pairs cancel, single elements survive, and that single property is the entire chapter.

The rest of the chapter is what falls out of that one identity when you bend the problem. Three variants and one warning.

Why hashing burns its space budget#

The hash-set answer is the loop you'd write if the bit-manipulation chapter wasn't open in front of you:

def single_number_hashset(nums):
    seen = set()
    for x in nums:
        if x in seen:
            seen.remove(x)
        else:
            seen.add(x)
    # exactly one element remains
    return next(iter(seen))

Correct. Also disqualified. The prompt's O(1) extra space constraint exists precisely to rule this out, because every interviewer has seen the hash answer and the question they're asking is whether you've seen the better one. The same is true of Counter in Python, HashMap<Integer, Integer> in Java, and unordered_map<int, int> in C++. They all carry O(n) state proportional to the number of distinct values.

The arithmetic trick 2 * sum(set(nums)) - sum(nums) is closer in spirit but brings its own problem: the multiplication overflows int in Java and C++ when the inputs are anywhere near 2^30, and the prompt's value range is [-2^31, 2^31 - 1]. XOR cannot overflow. The result of a ^ b always fits in the same width as a and b, because XOR is bit-by-bit: no carry, no propagation, no wider intermediate.^[1]

The pattern#

XOR over w-bit integers forms an abelian group (Z_2^w, ^) with identity 0, and every element is its own inverse.^[2] Four identities fall out, and the chapter rests on all four:

The first two collapse pairs to zero. The last two say it doesn't matter what order the pairs arrive in. Put the four together and the LC 136 algorithm writes itself: scan the array, XOR each element into a running accumulator, return the accumulator. After the scan, every twice-appearing value has been XORed in twice and contributes 0; the unique value has been XORed in once and contributes itself.

# LC 136. Single Number
from typing import List


def single_number(nums: List[int]) -> int:
    """LC 136 — element appearing once when every other element appears twice.
    O(n) time, O(1) space."""
    result = 0
    for x in nums:
        result ^= x
    return result

// LC 136. Single Number

public final class Sol {

    /** Pair-cancel reduction. O(n) time, O(1) space. */
    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int x : nums) {
            result ^= x;
        }
        return result;
    }

    private Sol() {}
}

// LC 136. Single Number

#include <vector>

// Pair-cancel reduction. O(n) time, O(1) space.
int singleNumber(const std::vector<int>& nums) {
    int result = 0;
    for (int x : nums) {
        result ^= x;
    }
    return result;
}

// LC 136. Single Number

package main

// singleNumber returns the lone element when every other appears twice.
// O(n) time, O(1) space.
func singleNumber(nums []int) int {
	result := 0
	for _, x := range nums {
		result ^= x
	}
	return result
}

The accumulator state on [4, 1, 2, 1, 2] traces out cleanly:

The intermediate values mean nothing on their own. Only the final state matters: pairs (1, 1) and (2, 2) self-cancel, and 4 is what remains.

When pairs become triples: LC 137#

Change the constraint. Every element appears three times except one. The hash-set instinct still works in O(n) space; the XOR instinct does not. XOR's pair-cancellation comes from x ^ x = 0, which is a fact about doubling. It says nothing about tripling. Three copies of the same value XORed together give back the value itself, not zero, and the algorithm dies on input [3, 3, 3, 7].

The fix is to drop one bit-position at a time and count. Each input value contributes 0 or 1 to each of 32 bit positions; the unique value's bit i is set if and only if the column-sum at position i is 1 mod 3. Reconstruct the answer one bit at a time.^[4]

# LC 137. Single Number II
#
# Per-bit count modulo 3: every other element contributes 0 (mod 3) to each
# bit position; only the unique element's bits survive. O(32n) = O(n) time,
# O(1) space. The three-state ones/twos accumulator is the same answer in
# fewer instructions and is harder to derive under interview pressure.
from typing import List


def single_number(nums: List[int]) -> int:
    """LC 137 — element appearing once when every other element appears three times."""
    result = 0
    for i in range(32):
        bit_sum = 0
        for x in nums:
            bit_sum += (x >> i) & 1
        if bit_sum % 3:
            # Bit i is set in the unique element. Mind the sign bit on i == 31.
            if i == 31:
                result -= 1 << 31
            else:
                result |= 1 << i
    return result

// LC 137. Single Number II
//
// Per-bit count modulo 3: O(32n) = O(n) time, O(1) space.

public final class Sol {

    public static int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            int bitSum = 0;
            for (int x : nums) {
                bitSum += (x >> i) & 1;
            }
            if (bitSum % 3 != 0) {
                result |= 1 << i;
            }
        }
        return result;
    }

    private Sol() {}
}

// LC 137. Single Number II
//
// Per-bit count modulo 3: O(32n) = O(n) time, O(1) space.

#include <vector>
#include <cstdint>

int singleNumber(const std::vector<int>& nums) {
    uint32_t result = 0;
    for (int i = 0; i < 32; ++i) {
        int bitSum = 0;
        for (int x : nums) {
            bitSum += (static_cast<uint32_t>(x) >> i) & 1u;
        }
        if (bitSum % 3 != 0) {
            result |= 1u << i;
        }
    }
    return static_cast<int>(result);
}

// LC 137. Single Number II
//
// Per-bit count modulo 3: O(32n) = O(n) time, O(1) space.

package main

func singleNumber(nums []int) int {
	var result int32
	for i := 0; i < 32; i++ {
		bitSum := 0
		for _, x := range nums {
			bitSum += (int(int32(x)) >> i) & 1
		}
		if bitSum%3 != 0 {
			result |= 1 << i
		}
	}
	return int(result)
}

The two nested loops are O(32 n), which is O(n) with a constant factor that doesn't show up in the asymptotic bound but does show up on the wall clock. There is a tighter solution: a two-bit finite-state machine that cycles 00 → 10 → 01 → 00 per bit position as inputs arrive in triples, running in true O(n) with no 32-factor.^[4:1] It's also the trick most candidates do not derive in an interview. Lead with the count-mod-3 voice; mention the state machine as the optimization, not as the answer.

The same shape generalizes. Every element appears k times except one uses the same per-bit count modulo k, and runs in O(32 n) for any k. The state-machine generalization exists for small k and gets opaque past k = 3.

When two elements survive: LC 260#

Change the constraint again. Every element appears twice except two distinct unique values. XOR the array now produces xor_all = a ^ b, where a and b are the two answers. That residue is non-zero (since a ≠ b), and any bit where it is set is a bit where a and b differ. Pick one such bit, partition the array by it, and each half is now a separate LC 136 instance.

The convention is to pick the lowest set bit, because there's a one-line idiom for it:

# LC 260. Single Number III
#
# Phase 1: XOR all -> xor_all = a ^ b (the two unique values).
# Phase 2: isolate any bit where a and b differ (lowbit = xor_all & -xor_all),
# bucket by that bit, XOR each bucket. Each bucket is now an LC-136 instance.
from typing import List


def single_number(nums: List[int]) -> List[int]:
    """LC 260 — two elements appear once; all others appear twice."""
    xor_all = 0
    for x in nums:
        xor_all ^= x
    diff_bit = xor_all & -xor_all  # isolate the lowest bit where a and b differ
    a = b = 0
    for x in nums:
        if x & diff_bit:
            a ^= x
        else:
            b ^= x
    return [a, b]

// LC 260. Single Number III
//
// XOR all -> xor_all = a ^ b. Bucket by lowest differing bit. Two LC-136s.

public final class Sol {

    public static int[] singleNumber(int[] nums) {
        int xorAll = 0;
        for (int x : nums) {
            xorAll ^= x;
        }
        // Note: when xorAll == Integer.MIN_VALUE, -xorAll == Integer.MIN_VALUE
        // and the AND still yields the sign bit alone. Java's two's-complement
        // int overflow on negation is well-defined; the idiom works unchanged.
        int diffBit = xorAll & -xorAll;
        int a = 0, b = 0;
        for (int x : nums) {
            if ((x & diffBit) != 0) {
                a ^= x;
            } else {
                b ^= x;
            }
        }
        return new int[] {a, b};
    }

    private Sol() {}
}

// LC 260. Single Number III
//
// XOR all -> xor_all = a ^ b. Bucket by lowest differing bit. Two LC-136s.

#include <vector>
#include <cstdint>

std::vector<int> singleNumber(const std::vector<int>& nums) {
    uint32_t xorAll = 0;
    for (int x : nums) {
        xorAll ^= static_cast<uint32_t>(x);
    }
    // Use unsigned negation so the lowest-set-bit idiom is well-defined
    // even when xorAll has only the high bit set.
    uint32_t diffBit = xorAll & (0u - xorAll);
    uint32_t a = 0, b = 0;
    for (int x : nums) {
        uint32_t ux = static_cast<uint32_t>(x);
        if (ux & diffBit) {
            a ^= ux;
        } else {
            b ^= ux;
        }
    }
    return {static_cast<int>(a), static_cast<int>(b)};
}

// LC 260. Single Number III
//
// XOR all -> xor_all = a ^ b. Bucket by lowest differing bit. Two LC-136s.

package main

func singleNumber(nums []int) []int {
	xorAll := int32(0)
	for _, x := range nums {
		xorAll ^= int32(x)
	}
	// int32 negation on MinInt32 wraps to itself; the lowest-set-bit
	// idiom still produces the sign bit alone, which is correct.
	diffBit := xorAll & -xorAll
	var a, b int32
	for _, x := range nums {
		if int32(x)&diffBit != 0 {
			a ^= int32(x)
		} else {
			b ^= int32(x)
		}
	}
	return []int{int(a), int(b)}
}

Trace on [1, 2, 1, 3, 2, 5]:

Phase 1 collapses paired elements; only 3 ^ 5 = 6 survives. The lowest set bit of 6 is bit 1, on which 3 and 5 disagree, so they fall into different buckets. Each bucket then resolves as an LC 136 instance.

Why x & -x extracts the lowest set bit#

The idiom is worth two sentences because it's the bit-manipulation tell most candidates miss. In two's complement, -x is ~x + 1: flip every bit of x, then add one. Below the lowest set bit of x, the bits of ~x are 1 and the carry from +1 propagates straight through them. At the lowest set bit, ~x has a 0, the carry stops, and the result has a 1 in that position. Above the lowest set bit, the bits of ~x are the complement of x. So x & -x matches x only at the lowest set bit, and that's the value the AND returns.^[5]

The dual idiom is x & (x - 1), which clears the lowest set bit and powers Kernighan's popcount loop in Bit manipulation primer. Mixing them up is the most reliable way to write a wrong LC 260 that passes some test cases. They are duals; the partition algorithm needs the extractor.

Two pitfalls that bite#

There are more, and the research notes for this chapter catalog all six. The two above are the ones every candidate fails on first contact.

What it actually costs#

The constant factors hide behind big-O on LC 137. Bit-position counting is 32 passes through the array; the state-machine is one. On n = 30,000 (the LC grader's typical upper bound) the difference is real but not decisive. Pick the count-mod-3 voice in an interview unless you've drilled the state machine to muscle memory.^[4:3]

Adjacent uses worth knowing#

LC 268 (Missing Number) is the same trick on a different shape. You're given n distinct integers from 0..n with one missing; XOR every index 0..n against every array value. Pairs (index i, value i) cancel except for the missing index, which XORs in once and survives. The arithmetic answer (n*(n+1)/2 - sum(nums)) also works but overflows int in Java and C++ once n crosses 2^15. XOR doesn't overflow.

LC 389 (Find the Difference) is the same trick on strings: XOR every character of the input against every character of the answer; the added character survives. Same algebra, different domain.

The XOR-prefix construction (prefix[i] = nums[0] ^ ... ^ nums[i-1], with range XOR prefix[r+1] ^ prefix[l]) is the bit-vector analogue of prefix-sum. Self-inverse plays the role that subtraction plays in prefix-sum: the shared prefix cancels.^[2:1] LC 1442 (Count Triplets That Can Form Two Arrays of Equal XOR) is the canonical use, and properly belongs to the bitmask-techniques chapter that follows this one.

Problem ladder#

CORE (solve all three to claim chapter mastery)#

• LC 136 — Single Number [Easy] • bit-xor-uniqueness ★
• LC 137 — Single Number II [Medium] • bit-position-counting
• LC 260 — Single Number III [Medium] • bit-xor-partition

STRETCH (optional)#

• LC 421 — Maximum XOR of Two Numbers in an Array [Medium] • bit-xor-trie-prefix (reference: Python only)
• LC 1707 — Maximum XOR With an Element From Array [Hard] • bit-xor-trie-offline (reference: Python only)

LC 268 (Missing Number) and LC 389 (Find the Difference) are strong honorary entries; they're omitted from CORE only to keep the ladder focused on the Single Number family. LC 191 and LC 461 live in Bit manipulation primer, where they belong.

Where this leads#

Bitmask techniques is next, and picks up where this chapter stops: subset enumeration, bitmask DP, and the XOR-prefix construction that powers LC 1442. Tries is the data-structure home for the LC 421 / 1707 family, which uses XOR as a maximization objective rather than a cancellation device. The two chapters trade the same problems back and forth; the pattern tag tells you which framing wins.

References#