# LeetCode Notes: Missing Number

## Question

Given an array `nums` containing `n` distinct numbers in the range `[0, n]`, return the only number in the range that is missing from the array.

Example 1:

Input: nums = [3,0,1]

Output: 2

Explanation**:** n = 3 since there are 3 numbers, so all numbers are in the range [0,3]. 2 is the missing number in the range since it does not appear in nums.

Example 2:

Input: nums = [0,1]

Output: 2

Explanation**:** n = 2 since there are 2 numbers, so all numbers are in the range [0,2]. 2 is the missing number in the range since it does not appear in nums.

Example 3:

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

Output: 8

Explanation**:** n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Example 4:

Input: nums = 

Output: 1

Explanation**:** n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

Constraints:

• `n == nums.length`
• 1 <= n <= 104
• `0 <= nums[i] <= n`
• All the numbers of `nums` are unique.

Follow up: Could you implement a solution using only `O(1)` extra space complexity and `O(n)` runtime complexity?

## Solution One

Analysis:

1. Sort the numbers in the array first
2. Traverse the array again to check whether the subscript and the value of the array can correspond, the uncorresponding number is the missing numebr
3. Finally, consider the case where there is only `0` and the case where the missing number is the last one

Code:

``````/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
const find = nums.sort((a,b) => a-b).findIndex((n,i) => {
return n !== i
})
return find !== -1 ? find : nums.length
};
``````

## Solution Two

Analysis:

Traverse the numbers of `0 - n` and check if they exist in the `nums` array. The numbers not in the `nums` array is the missing number.

Code:

``````/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
for(let i = 0; i < nums.length + 1; i++){
if(!nums.includes(i)){
return i
}
}
};
``````

## Solution Three

Analysis:

According to the above solution two, the performance of the `includes` method of directly using the array is not very good. We switch to the `Set` collection and use the `has` of the `Set` to find elements to improve query efficiency.

Code:

``````/**
* @param {number[]} nums
* @return {number}
*/
var missingNumber = function(nums) {
const set = new Set(nums)
for(let i = 0; i < nums.length + 1; i++){
if(!set.has(i)){
return i
}
}
};
``````