Solution: Missing Number in a Sorted List
This review discusses the solution of the missing number in a sorted list challenge in detail.
We'll cover the following...
Solution: 1
A naive solution to this problem is traversing through the whole list, starting from the first index and returning the missing integer as soon as we encounter it.
def missing_number(lst):"""Finds a missing number from the list which contains sorted numbers from 1 to onwards:param lst: List of sorted integers:return: Missing number in the sorted list"""actual_number = 1 # Grows in ascending orderfor i in lst: # Iterating the entire listif i is not actual_number: # If the number in the list is not equal to actual numberreturn actual_number # This is the missing number in the listactual_number = actual_number + 1 # Incrementing the actual number by 1return -1 # If there is no missing number# Driver code to test above functionif __name__ == '__main__':print(missing_number([1, 2, 4]))print(missing_number([1, 2, 3, 4, 6]))print(missing_number([2, 3, 4, 5, 6]))print(missing_number([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]))
Explanation
- Line 7:
actual_number
is initialized with 1 as the list is supposed to start with 1 - Line 10: Compare each element of the list with the
actual_number
- Line 11: If any number in the list doesn’t match with the
actual_number
then this is the missing number. Hence, return it - Line 14: Return
-1
if there is no missing number in the given sorted list
Time complexity
As the entire list is iterated over once, the ...