Single Number
easyTime: O(n)Space: O(1)
The shape of the problem
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
every element twice except oneno extra spaceXOR self-cancels
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.