Skip to main content
XOR Tricks

Single Number

XOR all elements together. Every duplicate pair cancels to 0, and the lone element XORed with 0 is itself. Result: the single unique element, in O(n) time and O(1) space. No hash map needed!

O(n)
·
O(1)

How It Works

XOR has two properties that make duplicate-elimination trivial: a value XORed with itself is zero, and XOR is commutative and associative. XOR every element of the array together and all paired values cancel, leaving exactly the element that appears once. No sorting, no hash set, no extra memory.

The same cancellation idea powers several variants: XOR of indices and values finds a missing number, and partitioning by a distinguishing bit separates two unique values. The scan is O(n) time and O(1) space, beating the O(n) space of a hash-set approach.

Step-by-Step Visualization

XOR all elements to find single number
4
0
1
1
2
2
1
3
2
4
XOR0 ⊕ 4 = 4
1/2

Code

Java
static int singleNumber(int[] nums) {
  int result = 0;
  for (int num : nums) result ^= num;
  return result;
}
// singleNumber(new int[]{4,1,2,1,2}) → 4

Tips & Gotchas

1XOR all elements: duplicates cancel out (a ⊕ a = 0)
2The result is the unique element (0 ⊕ x = x)
3Works because XOR is commutative and associative

Practice Problems

  • 1Single Number
  • 2Missing Number
  • 3Single Number III

About the XOR Tricks Pattern

XOR has a magical property: a ⊕ a = 0 and a ⊕ 0 = a. So if you XOR all elements in a list where every element appears twice except one, all pairs cancel out and the unique element survives.

Key insight

Key tricks: n & (n−1) clears lowest set bit (power-of-2 check). XOR of all elements cancels pairs. Bit masks can represent subsets for DP. These are often O(1) space solutions.

Common Bit Manipulation Interview Problems

  • Single Number
  • Number of 1 Bits
  • Counting Bits
  • Missing Number
  • Reverse Bits
  • Power of Two

Frequently Asked Questions

Why does XOR find the unique element without extra memory?

Because x ^ x = 0 and order does not matter, XORing the whole array cancels every value that appears an even number of times. The accumulator ends up holding exactly the odd-count element, using a single integer of state.

Does the XOR trick work when elements appear three times?

Not directly — pairs cancel but triples do not. The three-times variant (Single Number II) instead counts each bit position modulo 3, or uses a two-variable bitmask automaton, both still O(n) time and O(1) space.