Find Missing Number

ArrayBit ManipulationMath

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

Example 1

Input

[
  3,
  0,
  1
]

Output

Explanation. The numbers 0, 1, and 3 are present. The missing number is 2.

Example 2

Input

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

Output

Explanation. The numbers 0 to 6 and 9 are present. The missing number is 8.

Example 3

Input

[
  0
]

Output

Explanation. The only number present is 0, hence the missing number is 1.

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

Constraints:

1. The array will contain at least one number and at most 10,000 numbers. 2. Each element in the array is unique and ranges from `0` to `n`, inclusive, except for one missing number.

Views: 2