Find The Missing Number

ArrayBit ManipulationMath

Given an array of unique integers where each integer is between 1 and n (both inclusive) and where n is the length of the array plus one, there is exactly one number missing from this array. Your task is to identify and return this missing number.

Example 1

Input

[
  3,
  7,
  1,
  2,
  8,
  4,
  5
]

Output

Explanation. The number 6 is missing from the array which includes numbers from 1 to 7.

Example 2

Input

[
  1
]

Output

Explanation. The number 2 is missing from the array which was supposed to include numbers from 1 to 2.

Example 3

Input

[
  2,
  3
]

Output

Explanation. Number 1 is missing from the array which has numbers 2 and 3.

Follow-up: Can you solve the problem in linear time complexity and without using extra space, considering the modification of the input array is allowed?

Constraints:

The array has at least 2 numbers and no more than 10,000. All entries in the array are unique, and only one number is missing.

Views: 4