# 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:

1. 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

1. 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
};
``````