268. Missing Number — LeetCode(Python)

I got you!

Problem:

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.

Example 3:

Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9]. 8 is the missing number in the range since it does not appear in nums.

Example 4:

Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so all numbers are in the range [0,1]. 1 is the missing number in the range since it does not appear in nums.

Constraints:

• n == nums.length
• 1 <= n <= 104
• 0 <= nums[i] <= n
• All the numbers of nums are unique.

Solution(s):

1. Hashing —

Solution —

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        num_dict = {}
        for num in nums:
            if num not in num_dict:
                num_dict[num] = 1
                
        for num in range(len(nums)+1):
            if num not in num_dict:
                return num

Explanation —

We create a dictionary num_dict to store all numbers in the array nums. Then, we iterate over the range [0, n] to check for every number if it is stored in the dictionary. If a number is not in the dictionary, it is the number missing from the array nums and we return it.

Time and Space Complexity —

To iterate over the elements of the array to form a dictionary, is a linear time operation and the space needed to store all items in the dictionary is a linear function of the length of the input array.

Thus, if n is the length of the array nums,

Time Complexity: O(n)

Space Complexity: O(n)

2. Bit Manipulation —

Solution —

missing = len(nums)
for i in range(len(nums)):
    missing ^= i^nums[i]
return missing

Here, we use the XOR operation (^). The properties that we’ve used are:

a^a = 0

0^a = a

a^b = b^a

Thus, when we iterate over the array, we use the XOR operation on every single element with the variable missing and store the value of the expression in the same missing variable.

A sample run over the input array [0, 1, 3, 4] would be:

missing​=4∧(0∧0)∧(1∧1)∧(2∧3)∧(3∧4)

=(4∧4)∧(0∧0)∧(1∧1)∧(3∧3)∧2

=0∧0∧0∧0∧2

=2​

which is indeed the ‘missing’ element.

Time and Space Complexity —

To iterate over the elements of the array, is a linear time operation and we need constant space to store the variable missing.

Thus, if n is the length of the array nums,

Time Complexity: O(n)

Space Complexity: O(1)

3. Gauss’ Formula —

Solution —

expected_sum = len(nums)*(len(nums)+1)//2
actual_sum = sum(nums)
return expected_sum - actual_sum

Explanation —

We are aware of the fact that the sum of the first n natural numbers is represented as:

sum = (n * (n + 1)) / 2

We subtract this sum from the actual sum of the array that is passed as input to us and return the value. This value is equal to the number missing in the array.

Time and Space Complexity —

To sum over the elements of the array, is a linear time operation and we need constant space to store the mathematical and the actual sum.

Thus, if n is the length of the array nums,

Time Complexity: O(n)

Space Complexity: O(1)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏