Find the Missing Number

ArrayBit ManipulationMath

Given an array containing n distinct numbers taken from the range 0 to n, find the one number that is missing from the array. You may assume that no number in the range is missing more than once in the array.

Example 1

Input

[
  3,
  0,
  1
]

Output

Explanation. The numbers 0 through 3 are supposed to be present, but 2 is missing.

Example 2

Input

[
  0,
  1
]

Output

Explanation. The numbers 0 through 2 are supposed to be present, but 2 is missing.

Example 3

Input

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

Output

Explanation. The numbers 0 through 9 are supposed to be present, but 8 is missing.

Example 4

Input

[
  0
]

Output

Explanation. The numbers 0 through 1 are supposed to be present, but 1 is missing.

Follow-up: How would you solve this problem if large ranges are used and memory efficiency is critical?

Constraints:

The input array consists of unique integers ranging from `0` to `n`, where exactly one number within this range is missing.

Views: 3