Missing Number in Sequence

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 numbers 0, 1, and 3 are present. 2 is the missing number.

Example 2

Input

[
  0,
  1
]

Output

Explanation. The numbers 0 and 1 are present. 2 is the missing number since n equals 2.

Example 3

Input

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

Output

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

Follow-up: Can you implement a solution using O(1) extra space complexity and O(n) runtime complexity?

Constraints:

The input array will contain distinct integers.