Single Number - I
MediumXOR everything; the pairs vanish
Problem
Every element appears twice except one. Find the element that appears only once.
XOR everything — equal pairs vanish and the lone number survives.
The idea
XOR of a value with itself is zero, so every element appearing twice cancels and only the unique value survives. It runs in one pass with no extra memory, beating both sorting and a hash map.
The trick
- Order is irrelevant — XOR is commutative and associative.
- O(n) time, O(1) space.
4
1
2
1
2
0
1
2
3
4
acc0
Step 1 of 7. XOR has a magic property: a ^ a = 0 and a ^ 0 = a. So pairs cancel and the loner survives. Values: 4, 1, 2, 1, 2. acc 0.
1/7
Optimal
timeO(n)spaceO(1)
Fold with ^.
1// XOR everything; identical values cancel2let acc = 0;3for (const x of nums)4 acc ^= x;5return acc;Input
- array
- [4, 1, 2, 1, 2]
Memory
- i
- —
- acc
- 0
Output
- acc
- 0
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [2, 2, 1]
- Output:
- 1
- Explanation:
- The pair of 2s cancels, leaving 1.
Example 2
- Input:
- nums = [4, 1, 2, 1, 2]
- Output:
- 4
- Explanation:
- 1s and 2s pair off, leaving 4.
Example 3
- Input:
- nums = [9]
- Output:
- 9
- Explanation:
- One element is the answer.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.