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 must implement a solution with a time complexity better than O(n log n).

Example 1

Input

[
  3,
  0,
  1
]

Output

Explanation. The array has numbers from 0 to 3, but 2 is missing, hence the output is 2.

Example 2

Input

[
  0,
  1
]

Output

Explanation. The array has numbers from 0 to 2, but 2 is missing, hence the output is 2.

Example 3

Input

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

Output

Explanation. The array has numbers from 0 to 9, but 8 is missing, hence the output is 8.

Example 4

Input

[
  0
]

Output

Explanation. The array should have numbers from 0 to 1, but 1 is missing, hence the output is 1.

Follow-up: Can you solve the problem in linear time and without using extra space (apart from possibly modifying the input array)?

Constraints:

1 <= n <= 10^4. The array includes integers only and exactly one element is missing.

Views: 4