## Instructions

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

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

## Approach

We can find the sum of the current array, then find the sum of the array of numbers in the range between O and n. The difference between the two sums is the missing number.

Therefore, in this case we would have:

pseudocode:

```
sum1 = sum(nums)
sum2 = sum([0,1,2,3]
missing = sum2-sum1
```

### Python Implementation

```
def missingNumber(self, nums: List[int]) -> int:
return sum([i for i in range(0,len(nums)+1)]) - sum(nums)
```

The space complexity is O(1) and the time complexity is O(2n).

## Approach 2

Some mathematics and bit manipulation knowledge will come in handy for solving this problem.

Note: The XOR operator gives 1 as the output when the inputs are different and 0 when the inputs are the same. Therefore:

```
0^0 = 0
1^1 = 0
0^1 = 1
```

A number XORed by itself is equal to zero. Based on this knowledge we can compare the nums array to an array of all the integers in the range len(nums)+1 and find the missing element.

The image below demonstrates XOR operations.

XOR all numbers in the list of length n to get missing number.

### Python Implementation

```
def missingNumber(self, nums: List[int]) -> int:
r=0
for i,num in enumerate(nums):
r=r^i^num
return r^len(nums)
```

The space complexity is O(1) and the time complexity is O(n).

Useful Links

Missing Number

## Top comments (0)