Pattern Recognition Drill
Easy Bit Manipulation
The Problem
Every element appears twice except one. Find it.
What approach would you use?
Think about it before scrolling down.
XOR all elements. Pairs cancel to 0, leaving the unique element. O(n) time, O(1) space.
Count occurrences, find the one with count 1. O(n) time but O(n) space.
Common Trap
Hash set (add if absent, remove if present, remainder is answer) also works with O(n) space.