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

Useful Links
Missing Number