238. Missing Number
You receive an integer array nums holding n distinct values, each drawn from the range [0, n]. That range contains n + 1 candidates but the array only has room for n of them, so exactly one value from the range never shows up.
Return the value that is absent.
A sort makes this trivial — can you find the answer in one pass with constant extra memory?
Example 1:
Input: nums = [3, 0, 1]
Output: 2
Explanation: n = 3, so the full range is [0, 3]. The array covers 0, 1 and 3; the value 2 never appears.
Example 2:
Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Explanation: n = 9, range [0, 9]. Every value except 8 is present.
Constraints:
- n == nums.length
- 1 ≤ n ≤ 10⁵
- 0 ≤ nums[i] ≤ n
- All values in nums are distinct.
Hints:
If the array were sorted, the missing value would be the first index i where nums[i] != i (or n if no such index exists).
The sum 0 + 1 + ... + n is n(n+1)/2. What does subtracting the array's actual sum leave you with?
XOR is its own inverse: x ^ x = 0. XOR together every index 0..n and every array value — everything cancels except the missing number.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [3, 0, 1]
Expected output: 2