Question

How to find the missing number in a list containing numbers from 1 to n in O(1) time complexity with Python

Answer 1

"""
The essence of O(1) space complexity is that the algorithm uses a fixed amount of memory,
regardless of input size. Time complexity here is O(n) because we must scan the array.
"""

def find_missing_number(lst):
    size = len(lst)
    # formula for the sum of the first (size+1) natural numbers
    expected_sum = (size + 1) * (size + 2) // 2
    actual_sum = 0

    for num in lst:
        actual_sum += num

    return expected_sum - actual_sum


def main():
    lst = [1, 2, 4, 5, 6]
    
    missing = find_missing_number(lst)
    print("Missing number:", missing)


if __name__ == "__main__":
    main()



"""
run:

Missing number: 3

"""

 

70+ SQL courses for beginners and professionals