Single Number
Find the element that appears once when all others appear twice.
Pattern fit
XOR cancels pairs cleanly, so the answer survives exactly because equal numbers neutralize each other.
Key observation
a ^ a = 0 and a ^ 0 = a, so order does not matter.
Target complexity
O(n) / O(1)
How to break down the solution cleanly
XOR cancels pairs cleanly, so the answer survives exactly because equal numbers neutralize each other.
a ^ a = 0 and a ^ 0 = a, so order does not matter.
Define what each bit means.
Pick the one operation that naturally updates that meaning.
Reference implementation
Python# Generic pattern template
x & (x - 1) # clear lowest set bit
x & -x # isolate lowest set bit
x | (1 << i) # set bit i
x & ~(1 << i) # clear bit i
x ^ (1 << i) # toggle bit i
(x >> i) & 1 # read bit i
Common pitfalls
Overcomplicating the problem with maps when XOR is enough.
Not being able to explain why XOR order does not matter.
Common follow-ups
What if every other number appeared three times?
Why is XOR associative and commutative important here?
Continue with related problems
Build repeatable depth inside the Bit Manipulation cluster before moving on.