Missing Number in an Unsorted Array

Problem Given an array containing n distinct numbers drawn from the range [0, n], exactly one number in that range is missing. Find it.

Input / Output

• Input: int array nums of length n (distinct, all in [0, n]).
• Output: the missing number.

Constraints

• 0 ≤ n ≤ 10^4; aim for O(n) time and O(1) extra space.

Example

• [3,0,1] → 2; [0,1] → 2; [9,6,4,2,3,5,7,0,1] → 8.