Find the Missing Number

ArrayBit ManipulationMath

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

Example 1

Input

[
  3,
  0,
  1
]

Output

Explanation. The array contains numbers from 0 to 3 except for 2.

Example 2

Input

[
  0,
  1
]

Output

Explanation. The array contains numbers from 0 to 2 except for 2.

Example 3

Input

[
  9,
  6,
  4,
  2,
  3,
  5,
  7,
  0,
  1
]

Output

Explanation. The array contains numbers from 0 to 9 except for 8.

Example 4

Input

[
  0
]

Output

Explanation. The array should contain numbers from 0 to 1, but 1 is missing.

Follow-up: Can you implement a solution using a linear runtime complexity and without using extra space?

Constraints:

- The input array will not contain any duplicate numbers. - All numbers in the array are within the range from `0` to `n`.