...

/

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.

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.

Python 3.5
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 ...