DSA problem
Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
You should aim for a solution that runs in linear time and uses only constant extra space.
The XOR trick works because every index i from 0 to n and every value present in the array can all be XOR-ed together. Each number that appears both as an index and as a value cancels itself out (x ^ x = 0). The only index that has no matching value — the missing number — survives the cancellation and is returned.
Examples
Example 1
Input:
nums = [3,0,1]Output:
2Explanation: n = 3, so the range is [0,3]. The numbers 0, 1, 3 are present; 2 is missing.
Example 2
Input:
nums = [0,1]Output:
2Explanation: n = 2, so the range is [0,2]. The numbers 0 and 1 are present; 2 is missing.
Example 3
Input:
nums = [9,6,4,2,3,5,7,0,1]Output:
8Explanation: n = 9, so the range is [0,9]. Every number except 8 appears in the array.
Constraints
- n == nums.length
- 1 <= n <= 10^4
- 0 <= nums[i] <= n
- All the numbers of nums are unique.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.