The XOR Knight: Slaying Interview Problems with Bitwise Magic

The Quest Begins (The "Why")

I still remember the first time I faced a “single number” interview question. The prompt was simple: Given an array where every element appears twice except for one, find that lone element. My instinct was to reach for a hash map—count frequencies, then scan for the odd one out. It worked, but the interviewer’s eyebrow rose when I mentioned the extra O(n) space. “Can you do it in constant space?” they asked.

I spent the next twenty minutes scribbling on a whiteboard, trying to sort the array, then realizing that sorting would blow the O(n) time bound. I felt like a hero stuck in a side‑quest, missing the obvious shortcut. That frustration sparked a quest: Is there a way to crack this with just a few CPU instructions and no extra memory?

The answer, as it turns out, lives in the humble bitwise XOR operator—a tool many of us overlook because it looks too simple. Let’s embark on the journey to see why XOR is the secret weapon of the bitwise knight.

The Revelation (The Insight)

Why XOR?

XOR (exclusive‑or) has three magical properties that make it perfect for cancellation problems:

1. Self‑annihilation: a ^ a = 0.
2. Identity: a ^ 0 = a.
3. Commutative & associative: a ^ b ^ c = (a ^ b) ^ c = a ^ (b ^ c).

Because of (1) and (2), if you XOR a number with itself it vanishes, leaving only the untouched values. Thanks to (3), the order doesn’t matter—you can fold the entire array into a single accumulator and the paired numbers will cancel out, leaving the lonely one.

Think of it like a party where everyone shows up in pairs, wearing identical masks. When you‑name‑it shirts. As each pair enters the room, they spot each other, do a quick handshake, and disappear. The only guest without a twin wanders around, and when the music stops, that’s the one you see. XOR is the handshake that makes the pairs annihilate each other.

The “Aha!” Moment

I first saw this trick in a college algorithms lecture, but it didn’t click until I tried it on paper:

[4, 1, 2, 1, 2]  
4 ^ 1 ^ 2 ^ 1 ^ 2  
= (4) ^ (1 ^ 1) ^ (2 ^ 2)  
= 4 ^ 0 ^ 0  
= 4

The paired numbers vanished, leaving the answer in a single line of code. No hash map, no sorting, just a single pass. The interviewer’s grin was the real reward.

Wielding the Power (Code & Examples)

The Naïve Approach (the struggle)

def single_number(nums):
    freq = {}
    for x in nums:
        freq[x] = freq.get(x, 0) + 1
    for x, cnt in freq.items():
        if cnt == 1:
            return x

Pros: Straightforward, easy to explain.

Cons: O(n) extra space for the dictionary; two passes over the data.

The XOR Knight’s Solution (the victory)

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x          # cancel pairs, keep the lone wolf
    return result

Why it works: As we XOR each element, every number that appears twice contributes a ^ a = 0. Zero is the identity for XOR, so it doesn’t affect the accumulator. The solitary number never finds its twin, so it remains in result.

Complexity: One pass → O(n) time. Only two integer variables → O(1) space.

A Second Quest: Missing Number

Another classic interview problem: Given an array containing n distinct numbers from 0 to n, find the missing one.

Naïve (sum formula or hash set):

def missing_number(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    actual = sum(nums)
    return expected - actual

This works but risks overflow in languages with fixed‑size ints and still needs a full pass for the sum (still O(n) time, O(1) space, but relies on arithmetic that can fail).

XOR version (pure bitwise, no overflow concerns):

def missing_number(nums):
    n = len(nums)
    xor_all = 0
    # XOR all indices and all numbers
    for i in range(n + 1):
        xor_all ^= i
    for x in nums:
        xor_all ^= x
    return xor_all

Explanation: We XOR the complete set [0..n] with the given array. Every number that appears both in the range and the array cancels out (a ^ a = 0). The only value left is the missing one, because it never got a partner to annihilate with.

Complexity: Still O(n) time, O(1) space. No risk of integer overflow, works for any word size.

Common Traps to Avoid

1. Assuming sorted input – XOR works regardless of order; sorting adds O(n log n) time and defeats the purpose.
2. Using += instead of ^= – A simple typo turns the algorithm into a sum, losing the cancellation property.
3. Forgetting to initialize the accumulator to 0 – Starting with any other value would poison the result.

Why This New Power Matters

Mastering the XOR trick feels like unlocking a hidden combo in a fighting game: suddenly you can defeat bosses that once required elaborate strategies. In real‑world interviews, showcasing an O(1)‑space, O(n)‑time solution signals that you think beyond the obvious data structures and understand the underlying bit‑level mechanics.

Beyond interviews, the mindset spreads:

• Bitwise parity checks – quickly determine if a number has an odd number of set bits.
• Swapping without a temp variable – a ^= b; b ^= a; a ^= b; (though modern compilers often optimize the temp swap, it’s a fun demonstration of XOR’s reversibility).
• Finding duplicates in constrained ranges – the same principle extends to problems like “find the duplicate number” when numbers are in 1..n and exactly one repeats.

The elegance lies in the fact that we’re not adding complexity; we’re removing it by leveraging mathematics that the processor already performs in a single cycle.

Your Turn – Embark on Your Own Quest

Try this: Given an array where every element appears three times except for one that appears once, find that single element using only bitwise operations (hint: think about counting bits modulo 3).

Drop your solution in the comments, share a “gotcha” moment you hit while experimenting, or just tell me which bitwise trick you’ll wield next in your coding adventures. Happy hacking, and may your bits always line up just right!