Find Missing Number: using Python

Let us use this introductory problem to develop Algorithmic thinking

https://github.com/keon/algorithms

This is an easy level question, but we try to solve it in multiple ways. This example is intended to the beginners who are trying to improve their problem solving skills.

Problem Statement:

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.

Test Case examples:
Input: nums = [3,0,1]
Output: 2
Input: nums = [0,1]
Output: 2
Input: nums = [0]
Output: 1

Before jumping into the implementation, we shall develop our intuition by understanding the problem statement.

Let us imagine we have an array of size 6(length of the array) that consists of [3,2,1,0,6,5]. The task is to find the missing value from the given array. At a glance, we can say that 4 is missing, right. We will develop an algorithm to find this missing number.

Approach #1: Brute Force
Algorithm:
1. Scan through the array linearly in the range of length of the array(inclusive)
2. Check if the iterated value is in the array
3. Return the value if it is not in the array

def missingNumber(self, nums):
    n = len(nums)
        for num in range(length+1):#traversing through range of n
            if num not in nums:   #searching for the number in array
                return num        #returning the missing number

Time complexity : O(n²)
Space complexity: O(1)

The time complexity to search in an array is O(n) and since it is in a loop which scans linearly have O(n) time complexity. So the total time complexity is n*n or n² i.e.,for every iteration it looks at n items(in the worst case).
Since we haven’t used any space for storing except for length, which takes O(1), space complexity remains constant, O(1).

Approach #2: Modified Brute Force Using Set
The algorithm is same as the above with slight modification. We use set to store the array values and then search for the element which helps us improve with the performance drastically.
Algorithm:
1. Scan through the set linearly in the range of length of the array(inclusive)
2. Check if the iterated value is in the set
3. Return the value if it is not in the set

def missingNumber(self, nums):
        nums_set = set(nums)    #inserting array elements into a set
        length = len(nums)
        for num in range(length+1):#traversing through the array
            if num not in nums_set: #searching for the number in set
                return num

Time complexity : O(n)
Space complexity: O(n)

This is interesting! Just by implementing the set we were able to bring down the Time Complexity from O(n²) to O(n), How?
— The time complexity to search in a set is O(1), on average, where as for and since it is in a loop which scans linearly have O(n) time complexity. So the total time complexity is O(n).
Since we created a set of length that is equal to array, the space used is of size n, so space complexity is O(n).

In this approach, we were able to bring down the Time Complexity at the cost of Space complexity. This is called trade-off.

Approach #3: Gauss Formula
You should have heard the formula for sum of n natural numbers i.e., n*(n+1)/2. This is famously known as Gauss Formula. We will use this technique and solve our problem.

Algorithm:
1. Calculate the sum of n(length of the given array) numbers. Let this be sum_n
2. Calculate the sum of the elements in the array, let this be sum_ele
3. Return the difference between sum_n and sum_ele

def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        sum_of_n = ((n*(n+1))/2)  #sum of n numbers
        sum_of_elems = 0
        for num in nums:
            sum_of_elems += num    #total sum of elements in array
            
        return int(sum_of_n - sum_of_elems) #return missing number

Time Complexity:O(n)
Space Complexity: O(1)

We are traversing through the array linearly, i.e, O(n) Time complexity.
We haven’t used

This looks like an optimal solution. But this cannot be applied for a long long digit, because the calculation of the n*(n+1) results in an integer overflow.

We can solve this constraint using Bit Manipulation.

Approach #4: Using Bit Manipulation

This requires a bit of understanding of Bit Manipulation and the algorithm is pretty much simple as the above. This is much efficient than the above approach.

def missingNumber(self, nums):
        missing_num = len(nums)
        for i, num in enumerate(nums):
            missing_num ^= i^ num
        return missing_num

Time Complexity:O(n)
Space Complexity: O(1)

Feel free to comment. Please add/suggest other approaches.