Problem

**The task** is taken from LeetCode

Given an array containing n distinct numbers taken from

`0, 1, 2, ...,`

, find the one that is missing from the array.

n

Example 1:

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

Example 2:

`Input: [9,6,4,2,3,5,7,0,1] Output: 8`

Note:Your algorithm should run in linear runtime complexity. Could you

implement it using only constant extra space complexity?

**My approach** is to subtract the sum from 0-n and the sum of the elements in the array. For the sum of the number from `0`

to `n`

I use the *Gauss* forumula: `(n * (n + 1)) / 2`

. For the sum in the array I will have to iterate through the whole array and sum up the elements.

**My solution** has time complexity of O(n)

and space complexity of O(1)

$O(1)$.

```
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
if (nums.length === 0) return -1;
const sumOfNums = nums.reduce((ac, x) => ac + x);
const sumTillN = (nums.length * (nums.length + 1)) / 2;
return sumTillN - sumOfNums;
};
```

Solution

I don’t think there is a better than O(n)

$O(n)$and O(1)

$O(1)$to this problem.

However you can simplify the code a little (trivial) by subtracting from the expected total.

```
const findVal = nums => vals.reduce((t, v) => t - v, nums.length * (nums.length + 1) / 2);
```

Or

```
function findVal(nums) {
var total = nums.length * (nums.length + 1) / 2;
for (const v of nums) { total -= v }
return total;
}
```

BTW

The extra brackets are not needed when calculate the total

```
(x * (x + 1)) / 2 === x * (x + 1) / 2
```