Why it works
- xor flips each bit of result where num has a 1. A number that comes twice flips the same bits twice, so they end where they started: a xor a = 0, and x xor 0 = x.
- Flips do not depend on order: the two 10s are far apart, and in between result passes 9, 14 and 13, numbers that are not in the array. Only the end result counts.
- After every number, each bit of result is 1 exactly when an odd number of numbers had a 1 there. The pairs add an even count everywhere, so what is left are the bits of the single number.
Complexity
Time O(n): one pass, one xor per number. Memory O(1): a single number, no set or map.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗