Single Number
EasyXOR fold · pairs cancel
XOR cancels any number that appears twice, leaving only the one that's alone.
The idea
XOR every element together. Identical values cancel to zero (a ^ a = 0), so only the element that appears once survives the fold.
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.