Missing Number
EasyXOR index ⊕ value · pairs cancel
XOR all the numbers you have with all the numbers you should have; what's left is the missing one.
The idea
XOR all indices 0..n with all values. Every present number cancels with its index, leaving only the missing number behind.
3
0
1
0
1
2
acc3
Step 1 of 5. Start acc = n = 3. XOR in every index and value; matched pairs cancel, leaving the gap. Values: 3, 0, 1. acc 3.
1/5
Optimal
timeO(n)spaceO(1)
No overflow, no sum.
1let acc = n;2for (let i = 0; i < n; i++) acc ^= i ^ nums[i];3return acc;Input
- array
- [3, 0, 1]
Memory
- i
- —
- acc
- 3
Output
- acc
- 3
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 4, 5], n = 5
- Output:
- 3
- Explanation:
- The numbers 1..5 should be present; 3 is missing.
Example 2
- Input:
- nums = [1, 3], n = 3
- Output:
- 2
- Explanation:
- From 1..3, the number 2 is gone.
Example 3
- Input:
- nums = [2, 3, 4, 5], n = 5
- Output:
- 1
- Explanation:
- 1 is the one left out.
Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.