Timevolt

Posted on Aug 19

The Bitwise Awakening: XOR Tricks Every Competitive Programmer Should Know

#algorithms #datastructures #programming #coding

The Quest Begins (The "Why")

I still remember the first time I faced a problem that asked me to “find the element that appears only once while every other element shows up twice.” My initial instinct was to reach for a hash map, count frequencies, and then scan for the odd one out. It worked, but the solution felt clunky—extra O(n) space, a couple of loops, and a nagging feeling that there had to be a slicker way.

During a late‑night practice session, a friend tossed me a tip: “Try XOR‑ing everything together.” I blinked. XOR? The mysterious operator that flips bits? How could that possibly isolate a lonely number? Skeptical but curious, I typed it out, ran the test, and watched the correct answer pop out like a magic trick. That moment felt like discovering a hidden shortcut in a maze—one that turned a labor‑intensive slog into a single, elegant pass. I was hooked, and I knew I had to share why this works, not just how to type it.

The Revelation (The Insight)

The magic lies in two simple properties of the XOR (^) operator:

Self‑cancellation – a ^ a = 0. Any number XOR‑ed with itself vanishes.
Identity – a ^ 0 = a. Zero leaves a number unchanged.

XOR is also commutative and associative, meaning the order of operations doesn’t matter:

a ^ b ^ c = (a ^ b) ^ c = a ^ (b ^ c)

Now imagine we have an array where every value appears twice except one lonely value x. If we XOR the entire array, each pair a ^ a collapses to 0. All those zeros then XOR‑ together, still leaving 0. Finally, we have 0 ^ x, which is just x. The duplicates annihilate each other, and the survivor remains untouched.

It’s the same principle behind a balanced tug‑of‑war: equal forces on each side cancel out, leaving only the unopposed side to dictate the motion. No extra containers, no counters—just a single integer accumulator that we update in‑place.

Wielding the Power (Code & Examples)

The Struggle: Frequency Map

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

Pros: Straightforward, easy to read.

Cons: O(n) extra space for the hash map, two passes over the data, and a bit of boilerplate that feels unnecessary for such a simple task.

The Victory: XOR One‑Liner

def single_number(nums):
    result = 0               # start with the identity element
    for n in nums:
        result ^= n          # cancel pairs, keep the loner
    return result

Why it works: As we iterate, result holds the XOR of everything seen so far. Thanks to cancellation, every number that shows up an even number of times contributes zero to the final XOR. The lone odd‑occurrence number is the only thing left.

Common Traps

Starting with a non‑zero value – If you initialize result to something else (say, 1), you’ll end up with 1 ^ x instead of x. Remember: the identity for XOR is 0.
Using subtraction or addition – result -= n or result += n doesn’t have the self‑cancellation property; you’ll need to track counts explicitly.
Assuming it works for “three times” – The plain XOR trick only isolates a number that appears an odd number of times when all other numbers appear an even number of times. For “appears three times while others appear twice” you need a more sophisticated bit‑mask approach (which is a fun follow‑up quest!).

A Second Interview Twist: Two Lonely Numbers

Sometimes the prompt asks: “Find the two numbers that appear once while every other number appears twice.”

The XOR of the whole array gives us a ^ b (the XOR of the two unique values). This result has at least one bit set where a and b differ. We can use that bit to split the array into two buckets, XOR each bucket separately, and recover a and b.

def single_numbers(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n                     # a ^ b

    # Find a set bit (rightmost) where a and b differ
    diff_bit = xor_all & -xor_all

    a = b = 0
    for n in nums:
        if n & diff_bit:
            a ^= n
        else:
            b ^= n
    return a, b

The same principles apply—self‑cancellation within each bucket, identity element, and linear time.

Why This New Power Matters

Now you possess a bit‑wise scalpel that slices through problems that would otherwise demand auxiliary memory. In interviews, interviewers love to see that you recognize the XOR pattern because it signals:

Optimal space – O(1) extra memory, a huge win when constraints are tight.
Clean logic – No nested loops, no hash‑map gymnastics, just a tight, readable loop.
Versatility – The same idea extends to finding missing numbers, solving parity puzzles, and even cryptographic tricks.

When you drop the XOR solution, you’re not just answering the question; you’re showing you can think at the level of bits, the very foundation of how computers operate. That’s the kind of insight that turns a good candidate into a great one.

Your Turn: The Challenge

I’ve given you the sword; now go swing it. Here’s a mini‑quest for you:

Given an array where every element appears three times except for one that appears once, find that single element.

Hint: You’ll need to count bits modulo 3, but you can still do it in O(n) time and O(1) space using two integer masks.

Give it a try, share your solution in the comments, and let’s celebrate the moment when the bits line up just right. Happy hacking! 🚀

DEV Community