An array nums holds n distinct numbers drawn from the range 0 to n — so exactly one number of that range is absent. Return the missing number. The follow-up everybody gets: do it in O(n) time and O(1) space.
Examples
Example 1:
Input: nums = [3,0,1]
Output: 2
Example 2:
Input: nums = [0,1]
Output: 2
Explanation: n is 2, the range is 0..2, and 2 is absent.
Example 3:
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Example 4:
Input: nums = [0]
Output: 1
Constraints
1 <= nums.length <= 10^4
All values are distinct and within 0..nums.length.
Prerequisites
Binary and two's complement — how a negative number is stored, and what a shift does at the edges. The trick worth memorising: n & (n-1) clears the lowest set bit.
How to think about it
1. XOR Everything Together Optimal
Intuition
Fold every index and every value into one XOR. Each number that IS present appears twice — once as a value, once as an index — and cancels itself, leaving only the number that never appeared as a value. The sum formula n(n+1)/2 minus the actual sum works too; XOR avoids the overflow conversation entirely.
Algorithm
1. Start with n, the index the loop never reaches as a value. 2. XOR in every index and every value. 3. What survives is the missing number.
Time & Space
Time O(n). Space O(1) — which is the follow-up's requirement.