...

/

Solution: Missing Number in a Sorted List

Solution: Missing Number in a Sorted List

This review discusses the solution of the missing number in a sorted list challenge in detail.

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 order
for i in lst: # Iterating the entire list
if i is not actual_number: # If the number in the list is not equal to actual number
return actual_number # This is the missing number in the list
actual_number = actual_number + 1 # Incrementing the actual number by 1
return -1 # If there is no missing number
# Driver code to test above function
if __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 ...