Algorithms and Data Structures · Middle · Question 63 of 75
Every number in an array appears twice except one. How do you find it in O(n) time and O(1) memory?
- 1Count occurrences of every number in a hash map
- ✓Correct answer: XOR all numbers: pairs cancel, the single one remains
- 3Sort the array and compare neighboring values
Explanation
a ^ a = 0 and a ^ 0 = a, and XOR is commutative, so pairs vanish in any order. Sorting is O(n log n); a map is O(n) time but O(n) memory.