LeetCode 136 Single Number - Example and Complexity Analysis

Trace nums = [4,1,2,1,2].

result = 0.

result ^= 4: 0 ^ 4 = 4. result ^= 1: 4 ^ 1 = 5. result ^= 2: 5 ^ 2 = 7. result ^= 1: 7 ^ 1 = 6. result ^= 2: 6 ^ 2 = 4.

Answer: $4$.

In binary: 4 = 100, 1 = 001, 2 = 010. 100 ^ 001 = 101, 101 ^ 010 = 111, 111 ^ 001 = 110, 110 ^ 010 = 100 = 4.

$O(n)$ time, $O(1)$ space.