XOR in Coding Interviews: The Bit Trick Behind O(1) Space

Most engineers treat XOR like a weird relative at a family dinner. You know it's there. You nod at it. You have no idea what it does for work. Then an interview asks you to find the one number that appears once in an array where everything else appears twice, and suddenly you're reaching for a hash map while the interviewer watches you allocate O(n) space for a problem that needed five lines and zero data structures.

XOR is one of those tools that looks like magic until you see exactly how it works. Once you do, you'll spot it across a whole category of problems and know precisely what it does to your complexity numbers.

Two Properties Are All You Need

XOR (^) is a bitwise operator. For two bits, it returns 1 if they differ and 0 if they match. That's the whole definition. The useful part is what falls out algebraically.

The property that matters most is self-cancellation: a ^ a = 0 for any value of a.

Pair it with the identity: a ^ 0 = a. XOR-ing a value with itself erases it. XOR-ing with zero leaves it alone. Since XOR is also commutative (a ^ b == b ^ a) and associative ((a ^ b) ^ c == a ^ (b ^ c)), the order of operations doesn't matter.

Here's what that means in practice. Take the array [4, 1, 2, 1, 2]. XOR everything together:

4 ^ 1 ^ 2 ^ 1 ^ 2

Rearrange (legal, because commutative and associative):

(1 ^ 1) ^ (2 ^ 2) ^ 4
= 0 ^ 0 ^ 4
= 4

Every duplicate wiped itself out. The number with no pair survived. No hash map. No extra memory.

XOR cancellation: pairs cancel to 0, outlier survives Pairs cancel themselves to zero. The outlier has nothing to cancel with, so it rides through to the end.

Single Number Is the Template

LeetCode 136 asks you to find the element that appears exactly once when every other element appears exactly twice.

The naive solution reaches for a hash map: count frequencies, return the key with count 1. That's O(n) time and O(n) space. Correct, but the problem says "linear runtime complexity" and "constant extra space." The hash map flunks the second constraint, which is the one the interviewer actually cares about.

def singleNumber(nums: list[int]) -> int:
    result = 0
    for n in nums:
        result ^= n
    return result

One loop. One integer. The self-cancellation property does all the work. Pairs cancel to zero. The lone value XOR'd with zero returns itself.

Complexity: O(n) time, O(1) space.

This is the archetypal XOR pattern: a collection of duplicates with one outlier, and XOR's cancellation isolates the outlier for free. Five lines. The interviewer nods. You still have 27 minutes left.

Missing Number: XOR Works as a Range Check

LeetCode 268 gives you an array of n distinct numbers from [0, n] with one number missing. Return the missing one.

One approach: sum all numbers in [0, n] using n * (n + 1) / 2, subtract the array sum. Arithmetic, not XOR. It works, but XOR sidesteps any overflow risk when n is large.

The trick: XOR the full range [0, n] with every element in the array. Numbers that appear in both places cancel. The missing number only appears once, so it survives.

def missingNumber(nums: list[int]) -> int:
    result = len(nums)
    for i, n in enumerate(nums):
        result ^= i ^ n
    return result

We initialize result to n (the last index in the full range), then XOR each index i and each value n together. Everything in [0, n] that also appears in nums cancels. The missing number has no partner and remains.

O(n) time, O(1) space. No overflow concern, no extra allocation, no drama.

Single Number III: When Two Values Survive

LeetCode 260 escalates: now two unique values exist, and everything else appears twice. Straight XOR of the whole array gives you x ^ y. That's not enough on its own. You can't separate them from a single XOR result.

The resolution: find any bit where x and y differ. That bit is set in x ^ y. Use it to partition the array into two groups, numbers with that bit set and numbers without. The duplicates in each group cancel. One group is left with x, the other with y.

def singleNumber(nums: list[int]) -> list[int]:
    xor = 0
    for n in nums:
        xor ^= n

    diff_bit = xor & (-xor)

    x = 0
    for n in nums:
        if n & diff_bit:
            x ^= n

    return [x, xor ^ x]

xor & (-xor) isolates the lowest set bit. Two's complement flips all bits above the lowest set bit in -xor, so the AND extracts exactly that bit. Once you have x, you get y for free: xor ^ x.

Two passes, constant extra memory, O(n) time, O(1) space. The XOR pattern scales to two survivors by adding one partition step. If you derive this in an interview, you've just shown that you understand the mechanism rather than having memorized the trick.

The Same Trick Works Across Two Strings

LeetCode 389 gives you string s and string t, where t is s with one extra randomly-inserted character. Return that character.

XOR all the characters in both strings together. Every character in s has a match in t and cancels. The inserted character has no partner.

def findTheDifference(s: str, t: str) -> str:
    result = 0
    for c in s + t:
        result ^= ord(c)
    return chr(result)

Same shape as Single Number, applied to character codes. O(n) time, O(1) space. The sorting-based alternative is O(n log n). The hash map approach is O(n) time but O(n) space. XOR beats both. This is one of those problems where the "obvious" solution is measurably worse and the bit trick is the clean answer.

What XOR Does to Your Complexity

The pattern across all four problems is the same: XOR trades a data structure for arithmetic.

Wherever you'd track frequencies in a hash map to find the odd element out, XOR can often replace that hash map entirely. The space drops from O(n) to O(1). The time stays O(n). You're not doing anything clever per se. The algebra is just doing it for you.

This matters in interviews because "constant extra space" is your signal. Whenever a problem requires O(1) space and involves duplicates or missing values in a bounded range, XOR should be your first instinct. Think of it as the Bat-Signal for this problem class.

The tradeoff is specificity. XOR solves a narrow class of problems. It requires that values cancel in pairs. The moment you need to track arbitrary frequencies, or the pairing structure breaks (three of each instead of two), XOR alone won't work and you're back to hash maps or sorting.

LeetCode 137 (Single Number II, three of each) is the classic case where XOR fails. You need bit counting across 32 bit positions instead. Different tool. Knowing when a tool breaks is the part that separates "memorized the pattern" from "understands the mechanism."

Spotting XOR in Coding Interviews Takes Two Seconds

The tell-tale signals:

The problem says "every element appears exactly twice except one" or some variant.
You need to find a missing or extra value in a range where all other values are paired.
The problem explicitly asks for O(1) extra space.
Values are bounded integers, not arbitrary objects. XOR operates on bits.

If you see an "appears K times" problem and K is even, XOR is on the table. If K is odd and greater than one, you need bit counting. If the pairing structure doesn't exist at all, different strategy.

The cognitive move is: "pairs cancel, outlier survives." If the problem maps to that shape, write the XOR loop before the hash map. You'll finish faster, the code is shorter, and the complexity is better. Three wins.

Three Minutes, Done

An interviewer gives you Single Number. You see it immediately. You write five lines. You explain self-cancellation and why duplicates vanish. You name the complexity without being asked.

Three minutes. Six minutes left for follow-up. The interviewer asks what you'd do if elements appeared three times instead of two. You explain exactly why XOR breaks there and describe the bit-counting fallback.

That's the quality signal: not just knowing the trick, but knowing when it stops working.

If you want to practice these problems under real interview conditions with live feedback on your explanation, SpaceComplexity runs voice-based mock interviews that score your reasoning alongside your code. XOR problems are a good litmus test because the code is short and the explanation is everything.

What to Remember

a ^ a = 0 and a ^ 0 = a are the two properties. Commutative and associative, so order doesn't matter.
Single Number, Missing Number, and Find the Difference are the same pattern: pairs cancel, outlier survives.
Single Number III adds one step: isolate a differentiating bit, partition, XOR each group.
"O(1) space" in a problem with duplicates or bounded ranges is your cue to reach for XOR first.
XOR fails when values appear an odd number of times greater than one. That's bit counting territory.