Find the Missing Number

EasyArraysMathBit manipulation203 tests

You get an array nums with n distinct integers. Every value is between 0 and n, both included.

There are n + 1 numbers from 0 to n, but the array holds only n of them. So exactly one number is not in the array. Return that number.

The array is not always sorted.

Hint

You know the sum of all numbers from 0 to n: it is n * (n + 1) / 2. Compare it with the sum of the array. XOR works too: a value XOR itself is 0.

Try to use O(n) time and O(1) extra space.

Examples

Example 1

Input:: [4,0,1,5,2]
Output:: 3

n = 5, so the values should be 0, 1, 2, 3, 4 and 5. Only 3 is not in the array.

Example 2

Input:: [1,2,0]
Output:: 3

n = 3. The values 0, 1 and 2 are all there, so the missing one is 3 (the largest possible value).

Example 3

Input:: [1]
Output:: 0

n = 1, so the values should be 0 and 1. Only 1 is there, so 0 is missing.

Constraints

1 <= n == nums.length <= 40
0 <= nums[i] <= n
All values in nums are different.

Run checks your code against the 3 examples. Submit checks it against all 203 tests and needs a free account. You can also try ideas in the free JavaScript or Python compiler.