DEV Community

Timevolt
Timevolt

Posted on

The XOR Trick That Saved My Interview

#programming #coding #algorithms #datastructures

The XOR Trick That Saved My Interview

Quick context (why you're writing this)

I still remember the whiteboard interview where the interviewer slid a simple‑looking problem across the table: “Given an array where every element appears exactly twice except for one, find that single element.” My first instinct was to reach for a hash map or sort the array—both felt safe, but I could feel the clock ticking. After a few minutes of fumbling, I blurted out “What if we just XOR everything together?” The interviewer raised an eyebrow, I wrote the two‑line solution, and we moved on. That moment stuck with me because it showed how a tiny bit‑wise insight can turn an O(n log n) or O(n)‑space solution into pure O(n) time, O(1) space gold. If you’ve ever felt that “there has to be a cleaner way” while solving interview problems, you’re in the right place.

The Insight

XOR has a cancellation property: for any integer x, x ^ x = 0 and x ^ 0 = x. Moreover, XOR is associative and commutative, so the order of operations doesn’t matter. When you XOR a list where every value appears an even number of times, all those pairs collapse to zero, leaving only the values that appear an odd number of times.

Why does this work at the bit level? Look at a single bit position. XOR behaves like addition modulo 2: 0 ^ 0 = 0, 1 ^ 1 = 0, 0 ^ 1 = 1. If a bit is set in an even number of numbers, the modulo‑2 sum is 0; if it’s set in an odd number, the sum is 1. Doing this across all bit positions simultaneously gives you the exact number that survived the cancellations.

In short: XOR lets you erase pairs without extra memory, and whatever remains is the answer.

How (with code)

Here’s the cleanest version in Python (the same logic translates verbatim to C++, Java, JavaScript, etc.):

def single_number(nums):
    result = 0
    for n in nums:
        result ^= n          # cancel pairs
    return result
Enter fullscreen mode Exit fullscreen mode

What’s happening?

  • result starts at 0 (the identity for XOR).
  • Each iteration XORs the current element into result.
  • After processing the whole array, every number that appeared twice has contributed x ^ x = 0 twice, which is still 0. The lone number appears only once, so it stays in result.

Common mistakes

Mistake Why it’s wrong Fix
result = nums[0]; for n in nums[1:]: result += n Uses addition; duplicates don’t cancel, you end up with the sum of all elements. Replace + with ^.
seen = set(); for n in nums: if n in seen: seen.remove(n); else: seen.add(n); return seen.pop() Works but uses O(n) extra space. Use the XOR version for O(1) space.
return reduce(operator.xor, nums) (without initializing) If the list is empty, reduce throws an error. Provide an initial value: reduce(operator.xor, nums, 0).

The XOR approach is essentially one pass, constant extra memory, and no branching—the kind of solution interviewers love when they’re probing for bit‑wise fluency.

Why This Matters

  • Time complexity: We touch each element once → O(n). The inner operation (^) is a single CPU instruction, so the constant factor is tiny.
  • Space complexity: Only a single integer variable → O(1). No hash tables, no sorting, no recursion depth.
  • Interview impact: When you can replace a naïve O(n log n) or O(n space) solution with this, you instantly signal that you understand low‑level behavior and can think beyond library calls. It’s a classic “aha” moment that often leads to follow‑up questions like “What if two numbers appear once?”—which naturally extends to using XOR plus bit‑masking to split the array into two groups.

Beyond interviews, this trick shows up in real‑world scenarios: parity checks, cryptographic primitives, error‑detecting codes (like CRC), and even optimizing graphics shaders where you need to toggle bits efficiently.

A couple of interview‑style problems to try

  1. Single Number (LeetCode 136) – the problem we just solved.
  2. Single Number III (LeetCode 260) – Given an array where exactly two elements appear once and all others appear twice, return the two unique numbers. Hint: XOR the whole array to get x ^ y (the XOR of the two unique numbers). Find any set bit in that result (e.g., rightmost = xy & -xy). Use that bit to partition the array into two groups and XOR each group separately; each group will cancel its pairs and leave one of the unique numbers.

Give #2 a go—if you get stuck, think about how the rightmost set bit separates the two unique numbers into different buckets.

Challenge for you: Take an array of 32‑bit integers where every element appears three times except for one that appears once. Can you adapt the XOR idea (or a close variant) to find that single element in O(n) time and O(1) space? Drop your approach or a snippet in the comments—I’d love to see how you tackle it.

Happy bit‑twiddling!

Top comments (0)