Problem Statement
Single Number
You get a list of whole numbers called nums. Every number shows up exactly twice, except for one number that shows up only once. Your job is to find that lonely number. There are two extra rules: your solution has to be fast (it can only walk through the list one time, not loop over it again and again), and it can only use a tiny fixed amount of extra memory (you cannot build a big helper list or set that grows with the input).
Translate the prompt
Every element in the array appears exactly twice, except for one that appears once. Return the loner, in O(n) time and O(1) space.
Signals to notice
Brute force first
Hash map of counts, then walk it for the key with count 1. O(n) time, O(n) space — violates the space requirement.
The key insight
XOR is commutative, associative, and self-inverse. Folding it over the array collapses every duplicate pair to 0 regardless of where they sit.
Trace it on nums=[4,1,2,1,2]
acc=0 acc ^= 4 → 4 acc ^= 1 → 5 acc ^= 2 → 7 acc ^= 1 → 6 acc ^= 2 → 4 → return 4
What must stay true
After folding the first k elements with XOR, the accumulator equals the XOR of exactly the elements that have appeared an odd number of times so far.
Shape of the loop
acc = 0 for v in nums: acc ^= v return acc
Pseudocode only — the full worked solution lives in the Solution tab.
Easy way to go wrong
Initializing the accumulator to 1 instead of 0. `0 ^ x = x`, but `1 ^ x` flips the lowest bit and gives a wrong answer.