# LeetCode Notes: Numbers Missing From 0 to N-1

## Question

All numbers in an increasing sorted array of length n-1 are unique, and each number is in the range of 0 to n-1. There is only one number among n numbers in the range 0～n-1 that is not in the array. Please find this number.

**Example 1:**

Enter:[0,1,3]

Output:2

**Example 2:**

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

Output:8

**limit:**

`1 <= array length <= 10000`

## Solution

**Analysis:**

- Try to use
`reduce`

to solve, run the following program

```
[0,1,2,3,5,6].reduce((a,b)=>{
console.info(a,b)
return a + 1
})
// output
0 1 // Difference by 1
1 2 // Difference by 1
2 3 // Difference by 1
3 5 // Difference 2
4 6 // Difference 2
```

We find that when the difference between b and a is 2 for the first time, it is the position of the default number we are looking for, which is `a+1`

, where the result is 4

- After testing, it is found that there are two special cases, namely the default numbers at the beginning and the end. Run the following program

Default 6

```
[0,1,2,3,4,5].reduce((a,b)=>{
console.info(a,b)
return a + 1
})
// output
0 1
1 2
2 3
3 4
4 5
```

as well as Default 0

```
[1,2,3,4,5].reduce((a,b)=>{
console.info(a,b)
return a + 1
})
// output
1 2
2 3
3 4
4 5
```

We found that none of them have a difference of 2 between b and a. Two steps:

- Directly determine whether the beginning of the array is 0, if it is not 0, directly return to the default value of 0
- The next step is to traverse the array to find if there is a
`b-a = 2`

situation, if not, you can determine that the default number is at the end of the array

**Code:**

```
/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
// Special treatment 0 does not exist
if(nums[0] !== 0) return 0
let result = 0
nums.reduce((a,b)=>{
// The first time the difference is 2, the number between a and b is the default number
if(b-a === 2 && result === 0){
result = a + 1
}
return a + 1
})
// result is always equal to 0, indicating that there is no difference between b and a by 2, it can be determined that the default is the last number, and the length of the array is the result value
return result === 0? nums.length: result
};
```

## Comments