DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Bernice Waweru
Bernice Waweru

Posted on

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
Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Python Implementation

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

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
Enter fullscreen mode Exit fullscreen mode

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
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)
Enter fullscreen mode Exit fullscreen mode

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

Useful Links
Missing Number

Top comments (0)

🌚 Friends don't let friends browse without dark mode.

Sorry, it's true.