## DEV Community 👩‍💻👨‍💻 is a community of 930,237 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# Find Missing Number in an Array.

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