Missing Number

Problem Given an array containing n distinct numbers drawn from the range [0, n], find the single number in that range which is missing from the array.

Input / Output

• Input: array nums of n distinct integers, each in [0, n]
• Output: the one integer in [0, n] not present in nums

Constraints

• 1 <= n <= 10^4; all values distinct and within [0, n]
• Exactly one number is missing
• Target O(n) time and O(1) extra space — the interviewer will reject sorting or a hash set

Example

• [3,0,1] → 2
• [0,1] → 2 (the missing number is at the top of the range)
• [9,6,4,2,3,5,7,0,1] → 8