# Missing Number - LeetCode Daily Challenge

## Problem Statement

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

**Follow up:** Could you implement a solution using only `O(1)`

extra space complexity and `O(n)`

runtime complexity?

### 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.
```

Try here before watching the video.

### Video Solution

## Approach

### A. Sorting

We can solve this problem using Sorting, where we can sort the array and then find which number is missing. **Time Complexity: O(N * logN)Space Complexity: O(1)**

### B. HashMap

A brute force method for solving this problem would be to simply check for

the presence of each number that we expect to be present. The naive

implementation might use a linear scan of the array to check for containment,

but we can use a `HashSet`

to get constant time containment queries and

overall linear runtime.**Time Complexity: O(N)Space Complexity: O(N)**

### C. Bit Manipulation

Because we know that `nums`

contains `n`

numbers and that it is missing

exactly one number in the range [0..n−1]. We are also aware of the fact that the **XOR **of a number to itself is `0`

. Therefore, if we initialize an integer

to n and XOR it with every index and value, we will be left with the

missing number. Consider the following example:

Index | 0 | 1 | 2 | 3 | |
---|---|---|---|---|---|

Value | 0 | 1 | 3 | 4 |

missing = 4 ^ (0 ^ 0) ^ (1 ^ 1) ^ (2 ^ 3) ^ (3 ^ 4)

missing = 4 ^ 0 ^ 0 ^ 2 ^ (3 ^ 3) ^ 4

missing = (4 ^ 4) ^ 2 ^ (3 ^ 3)

missing = 2 **Time Complexity: O(N)Space Complexity: O(1)**

### Java Code

```
class Solution {
public int missingNumber(int[] nums) {
int missing = nums.length;
for (int i = 0; i < nums.length; i++) {
missing ^= i ^ nums[i];
}
return missing;
}
}
```

### C++ Code

```
class Solution {
public:
int missingNumber(vector<int>& nums) {
int missing = nums.size();
for (int i = 0; i < nums.size(); i++) {
missing ^= i ^ nums[i];
}
return missing;
}
};
```

### Python Code

```
class Solution:
def missingNumber(self, nums):
missing = len(nums)
for i, num in enumerate(nums):
missing ^= i ^ num
return missing
```

### Javascript Code

```
var missingNumber = function(nums) {
let missing = nums.length;
for (let i = 0; i < nums.length; i++) {
missing ^= i ^ nums[i];
}
return missing;
};
```

### Go Code

```
func missingNumber(nums []int) int {
missing := len(nums)
for i := 0; i < len(nums); i++ {
missing ^= i ^ nums[i]
}
return missing
}
```

### Complexity Analysis

**Time Complexity: O(N)Space Complexity: O(1)**