Missing Number in Array

easy

Given an array containing n distinct numbers taken from 0 to n, find the one number that is missing from the array. For instance, given the array [3, 0, 1], the number 2 is missing. Your solution should run in linear runtime complexity and use only constant extra space.

Example 1

Input

Output

Explanation. The sum of numbers from `0` to `3` is `6` and the sum of the array `[3, 0, 1]` is `4`. Hence, the missing number is `6 - 4 = 2`.

Example 2

Input

Output

Explanation. The sum of numbers from `0` to `9` is `45` and the sum of the array `[9,6,4,2,3,5,7,0,1]` is `37`. Therefore, the missing number is `45 - 37 = 8`.

Example 3

Input

[
  [
    0
  ]
]

Output

Explanation. The expected number should be `1` as it's the missing number when considering the range from `0` to `1`.

Follow-up: Can you implement a solution using a mathematical formula to compute the missing number directly?

Constraints:

The length of the array is at least 1 and at most 10,000. All elements are unique.