Missing Number

You are given an array nums containing n distinct numbers taken from the range 0 through n.

Exactly one value in that range is missing. Return the missing number.

Input / output

• Input: nums: int[]
• Output: the missing integer in [0, n]

Examples

1. nums = [3, 0, 1] returns 2.
2. nums = [0, 1] returns 2.
3. nums = [9,6,4,2,3,5,7,0,1] returns 8.

Constraints

• 1 <= nums.length <= 100000
• 0 <= nums[i] <= nums.length
• All values in nums are distinct.

Edge cases

• The missing value may be 0.
• The missing value may be n itself.
• The input is not guaranteed to be sorted.

Target complexity

• Aim for O(n) time and O(1) extra space.

Hints

1. Compare the expected sum of 0 + 1 + ... + n with the actual array sum.
2. The XOR trick also works because equal values cancel each other.

Follow-up What other constant-space approach can you derive using XOR instead of arithmetic sums?