Missing Number

Problem: Given an array containing n distinct numbers taken from the range [0, n], find the one number in the range that is missing from the array.

Constraints: Array length n, values in [0, n].

Example: [3,0,1] -> 2. [0,1] -> 2. [9,6,4,2,3,5,7,0,1] -> 8.

Approach: Compute the expected sum of 0..n using n*(n+1)/2, subtract the actual sum of the array — the difference is the missing number. O(n) time, O(1) space. (XOR of all indices and values is an equally valid O(1)-space alternative.)