Imagine you're at a party. Everyone came with a partner — except one person. There's no guest list. How do you find the person without a partner, in O(n) time, without using any extra space?
Sounds impossible, right?
Well, this is EXACTLY the problem XOR solves. And it's NOT just a party trick — this property appears in Amazon, Google, Meta interviews constantly. The "I've seen this before" factor in these interviews is REAL.
Let's first understand our 4 superhero XOR properties. These are your weapons:
Tip
💡 The Key Insight: The combination of Self-Cancellation (x ^ x = 0) + Commutative + Associative is the SECRET SAUCE. When you XOR every element in an array,pairs cancel out. Whatever's left is the element with no pair.
1. XOR Cancellation Property — The Deep Intuition
Let's really UNDERSTAND why x ^ x = 0 works. Not just memorize it.
Binary Level Intuition
XOR at the bit level is "different = 1, same = 0".
5 = 101
5 = 101
-----------------
5 ^ 5 = 000 = 0
Every single bit is the SAME in both numbers. So every bit position → 0. The entire number becomes 0. That's it!
Now here's the MAGIC — because XOR is commutative and associative, we can rearrange and group any sequence of XOR operations:
🔑 The Cancellation Superpower: Every number that appears TWICE in an XOR operation effectively "removes itself". The only number that survives is the one that appears ONCE. This works for any pair of equal numbers, regardless of where they appear in the array!
2. Find Unique Element — Single Number
Problem: Given an array where every element appears twiceexcept one, find that single element.
Note
🍬 Real-World Analogy: Imagine you're at a candy shop where every candy comes in pairs — except one. The shopkeeper says, "Find the lone candy, and it's yours!" You could check each candy by writing down every candy you see (that's the hash map approach). But XOR is like having a magic eraser: every time you see a candy, you either add it or erase it. Pairs erase each other. Only the unique candy remains. 🎯
🔍 Real-Time Thinking — What Do I Know?
"OK, so every element appears twice except one. Let me think... If I use a hash map, that's O(n) space. But what if I could somehow make pairs cancel out? Hmm, is there an operation where x OPERATOR x = 0? That's XOR! x ^ x = 0. And XOR is commutative too, so order doesn't matter. So if I XOR everything, pairs cancel to 0, and 0 ^ x = x. The unique element survives! Let me verify: [2,3,1,3,2] → 2^3^1^3^2 = (2^2)^(3^3)^1 = 0^0^1 = 1. YES! That's it."
🤔 Let's Think About It
Take a moment. If you'd never seen XOR before, how would you solve this?
🤔 The Decision: Include or Cancel?
Every time I XOR a new number, I'm making a decision: "Do I keep this number, or does it cancel something I've already seen?" If I've seen this number before, the XOR will cancel it out (x ^ x = 0). If it's new, it stays in the accumulator. This is the choose/not-choose framework: each element either chooses to pair up (if its twin is already in the accumulator) or chooses to stay (if it's the unique one). The beauty is I don't need to track which is which — XOR handles it automatically!
Brute Force Approach
function findUniqueBrute(arr) {
const map = new Map();
for (const num of arr) {
map.set(num, (map.get(num) || 0) + 1);
}
for (const [num, count] of map) {
if (count === 1) return num;
}
}
✅ This works! But it uses O(n) extra space. Can we do better?
✨ The XOR Optimal Solution
Remember our party analogy? Every pair cancels out. The single element survives. This is EXACTLY what XOR does!
📋 Edge Cases to Consider
Single element array: The loop runs once, XOR with 0 returns the element itself. Works automatically.
Negative numbers: Bitwise XOR works on 32-bit two's complement representation. No issues.
All same numbers except one: e.g., [7, 7, 7, 7, 3] — pairs cancel, 3 remains. Only works if the unique element appears exactly once.
Zero as the unique element: e.g., [5, 0, 5] — 5^0^5 = 0. XOR correctly returns 0.
Large numbers beyond 32-bit: JavaScript bitwise ops truncate to 32-bit signed. For larger numbers, use BigInt.
function findUnique(arr) {
let xor = 0;
for (const num of arr) {
xor ^= num; // XOR current number — pairs will cancel
}
return xor; // The unique element remains
}
📊 Dry Run — Watch It In Action
Let's trace through findUnique([2, 3, 1, 3, 2])step by step. This is where the intuition CLICKS:
Step
Current Number
xor BEFORE
Operation
xor AFTER
What Happened?
1
2
0
0 ^ 2
2
First number, just stored it
2
3
2
2 ^ 3
1
Different numbers → new XOR value
3
1
1
1 ^ 1
0
SAME number → cancelled! (1 ^ 1 = 0)
4
3
0
0 ^ 3
3
0 XOR anything = that thing
5
2
3
3 ^ 2
1
🔥 The SECOND 2 arrived and cancelled! Result = 1
Edge Cases
Empty array? Returns 0 (but problem guarantees at least one element)
Single element? Returns that element directly (xor starts at 0, 0 ^ x = x)
Negative numbers? XOR works on the binary representation — no issues!
Large numbers? JS uses 32-bit signed integers for bitwise ops — safe for typical constraints
Tip
⚡ Interview Tip: When you hear "appears twice except one" in an interview, your brain should immediately think XOR. Say it out loud: "I can XOR all elements — pairs cancel out, leaving the unique element." This shows the interviewer you've seen this pattern before.
PROBLEMSingle Number
Solve it yourself! Every element appears twice except one. Find the unique element.
Loading playground...
3. Missing Number & Duplicate Patterns
Problem: Given an array containing n distinct numbers taken from 0 to n, find the one that's missing.
For example: [3, 0, 1] should return 2(n=3, but 2 is missing).
Note
🎪 Real-World Analogy: Imagine a concert where tickets are numbered 0 to n. You collect tickets at the entrance. At the end, you realize one ticket number is missing from your collection. You know all ticket numbers from 0 to n were issued. How do you find which one was never collected? XOR the issued numbers with the collected numbers — the missing number survives! It's like having the guest list AND the attendance list, and finding who didn't show up.
The XOR Trick Extended
This is where things get interesting. We don't just have one array — we have TWO arrays:
The given array (with the missing number)
The "perfect" array (all numbers from 0 to n)
🔍 Real-Time Thinking — What Do I Know?
"So I have an array of n numbers from 0 to n, but one is missing. The range is [0, n]. I know all numbers in the range. What if I XOR the range 0..n with the array? Every number that appears in BOTH cancels out. The missing number appears only in the range (once) and not in the array — so it survives. Let me check: [3, 0, 1] → missing is 2. Range 0..3 = 0123. XOR all: (0^0)^(1^1)^2^(3^3) = 0^0^2^0 = 2. Perfect! And I can even do this in one pass by XORing index i with nums[i] as I go."
function missingNumber(nums) {
const n = nums.length;
let xor = 0;
// XOR all numbers from 0 to n
for (let i = 0; i <= n; i++) xor ^= i;
// XOR with all numbers in array
// Pairs cancel, missing number remains
for (const num of nums) xor ^= num;
return xor;
}
// Even cleaner: do it in ONE pass!
function missingNumberOnePass(nums) {
const n = nums.length;
let xor = 0;
for (let i = 0; i < n; i++) {
xor ^= i ^ nums[i]; // XOR index and value together
}
return xor ^ n; // Don't forget to XOR the last number
}
Key Insight
🔑 Pattern: When you have a "range from 0 to n" and need to find what's missing — XOR the range with the array. Every number that's in BOTH cancels out. The missing number (which only appeared once) survives!
PROBLEMMissing Number
Given an array of n distinct numbers from 0 to n, find the missing one.
Loading playground...
PROBLEMFind the Difference
You are given two strings s and t. String t is generated by shuffling s and adding one extra character. Find that character.
Loading playground...
PROBLEMDecode XORed Array
The XOR of adjacent elements is given — reconstruct the original array from the first element and the XOR prefixes.
Loading playground...
Warning
⚠️ Common Mistake: XOR works GREAT for "missing number" but ONLY because the numbers are in a known range (0 to n). If the problem says "array of arbitrary integers where one is missing", XOR won't help — use sum formula instead:missing = expectedSum - actualSum.
4. XOR Among Triples — When XOR Alone Isn't Enough
Problem: Now EVERY element appears THREE times, except one element that appears once. Find it.
Here's the thing: XOR cancellation works for PAIRS. But triples? If you XOR three 5's: 5 ^ 5 ^ 5 = 0 ^ 5 = 5. They DON'T cancel! We need a different approach.
Note
🍕 Real-World Analogy: Imagine a pizza party where most people come in groups of three — except one person who came alone. XOR can't help because three of a kind don't cancel (5^5^5 = 5). But here's the trick: look at each seat at the table (each bit position). Count how many people are sitting at each seat. If the count isn't divisible by 3, that seat must belong to the lone person!
The Bit Counting Approach
Since each element appears 3 times (except one), at every bit position, the total count of 1's must be divisible by 3. If it's NOT divisible by 3, that bit belongs to our unique element!
📋 Edge Cases to Consider
All numbers appear three times except one: The bit-count modulo 3 approach works for ANY k, not just 3.
The unique element is 0: If the unique element is 0, no bit will have count % 3 !== 0. Result stays 0. Correct!
Single element array: Only one element, no triples. Each of its bits has count = 1 (not divisible by 3). All bits are included.
All elements same: If all appear 3 times, count % 3 = 0 for all bits. Result = 0. But problem guarantees one unique element.
Negative numbers (32-bit): JavaScript's 32-bit signed integers work fine — the sign bit (bit 31) is handled like any other.
Algorithm
function singleNumberII(nums) {
let result = 0;
// Check each bit position (32 bits for integers)
for (let bit = 0; bit < 32; bit++) {
let count = 0;
// Count how many numbers have this bit set
for (const num of nums) {
if ((num >> bit) & 1) count++;
}
// If count is NOT multiple of 3, this bit is in the unique number
if (count % 3 !== 0) {
result |= (1 << bit);
}
}
return result;
}
Key Insight
🔑 The Intuition: XOR works for pairs because x ^ x = 0 (pair cancels). For triples, we can't use XOR directly — but we CAN use the fact that at any bit position, the count of 1's is either 3k or 3k+1. The remainder tells us which bits belong to our unique element!
PROBLEMSingle Number II
Every element appears THREE times except one. Find the element that appears once.
Loading playground...
5. Two Unique Elements — The Set Bit Partition
Problem: Now there are TWO elements that appear once. Everything else appears twice. Find both unique elements.
Note
👫 Real-World Analogy: Imagine a party where everyone came with a partner — except TWO people who came alone. XOR everything and pairs cancel, leaving x^y (the XOR of the two singles). Now you have the XOR of two unknowns. How do you separate them? Find ANY bit where they differ (a set bit in x^y), then partition the crowd: "Everyone with this bit set on your nametag goes to room A, everyone without it goes to room B." Each room then has one single plus some pairs that cancel!
🤔 Think About It
We XOR everything. Pairs cancel. We get x ^ y(two unique numbers XOR'd together). But that's just ONE value — how do we separate x from y? This is where the REAL bit manipulation genius shines!
function singleNumberIII(nums) {
// Step 1: XOR all — get x ^ y
let xorAll = 0;
for (const num of nums) xorAll ^= num;
// Step 2: Find any set bit in xorAll
// This bit is DIFFERENT between x and y
const setBit = xorAll & (-xorAll); // Isolate lowest set bit!
// Step 3: Partition numbers by this bit
let x = 0, y = 0;
for (const num of nums) {
if (num & setBit) {
x ^= num; // Numbers with this bit set — includes x
} else {
y ^= num; // Numbers without this bit — includes y
}
}
return [x, y];
}
Key Insight
🔑 The Genius Trick:xorAll & (-xorAll) isolates the LOWEST SET BIT. Why? In two's complement, -xorAll = ~xorAll + 1. The only bit that survives is the rightmost 1. This bit separates our two unique numbers — one has it set, the other doesn't!
PROBLEMSingle Number III
Two elements appear only once, all others appear twice. Find both unique elements.
Loading playground...
6. XOR Properties — Complete Reference
Property
Rule
Example
Use Case
Identity
x ^ 0 = x
5 ^ 0 = 5
Starting point (xor = 0)
Self-Cancel
x ^ x = 0
5 ^ 5 = 0
🔥 Cancelling pairs!
Commutative
x ^ y = y ^ x
3 ^ 5 = 5 ^ 3
Order doesn't matter
Associative
(x ^ y) ^ z = x ^ (y ^ z)
(3 ^ 5) ^ 2 = 3 ^ (5 ^ 2)
Group any pair
Same
x ^ y = 0 ⟺ x = y
5 ^ ? = 0 → ? = 5
Check equality
Toggle
x ^ y ^ y = x
5 ^ 7 ^ 7 = 5
Flip back and forth
Missing
x ^ y = z → x = y ^ z
5 ^ 3 = 6 → 5 = 3 ^ 6
Decode XOR arrays
Tip
⚡ Pro Tip: Commit the "Missing" property to memory:x ^ y = z ⟺ x = y ^ z ⟺ y = x ^ z. This means if you know any two of the three values in an XOR equation, you can find the third. This is the basis of Decode XOR Array problems!
🎯 Interview Cheat Sheet
Key Insight
Q1: When should I use XOR vs a hash map? XOR when: space is limited (O(1)), or "pairs cancel out" pattern. Hash map when: you need more info than cancellation (like position-based queries).
Key Insight
Q2: Does XOR work for negative numbers? YES! In JavaScript, bitwise operators treat numbers as 32-bit signed integers. The cancellation property (x ^ x = 0) works regardless of sign.
Key Insight
Q3: How do I isolate the rightmost set bit? n & (-n). In two's complement, -n = ~n + 1. Only the rightmost 1 bit survives. This is a CRITICAL pattern for bit problems.
Key Insight
Q4: Can XOR detect if exactly one bit is set? Yes! n > 0 && (n & (n-1)) === 0. This clears the lowest set bit — if the result is 0, there was only ONE set bit.
Key Insight
Q5: What if the problem says "appears k times except once"? General pattern: count bits modulo k. At each bit position, if count % k !== 0, that bit belongs to the unique element. This works for ANY k!
📝 Key Takeaways
XOR cancellation (x ^ x = 0) is your primary weapon for "find unique element" problems
Start with xor = 0 — identity property means 0 ^ x = x, so the first element just gets stored
"Appears twice except one" → XOR — this should be your INSTANT reaction in interviews
"Appears k times except one" → bit counting modulo k — XOR alone doesn't work for triples
Two unique elements — XOR all to get x^y, then use xorAll & (-xorAll) to partition
Missing in range — XOR the range with the array. Range numbers cancel array numbers, missing survives
Set bit isolation — n & (-n) is the standard pattern, memorize it!
Time: O(n), Space: O(1) — XOR solutions are always optimal on space
XOR works on ALL numbers — negatives, large values, it doesn't matter. Bitwise is universal
Practice! — The only way this becomes intuitive is by solving problems. The Playground is your dojo 🥋
Note
🔮 What's Next? Now that you've mastered XOR cancellation, head over to Bit Counting to learn about popcount and Hamming distance!