PYTHON

find mising number in O(n)

#let group A be subset of {1,2,3,...,n} s.t. |A|=n-1
# arr=[all the numbers from A]
def find_missing_number(arr: list[int]) -> int:
    n: int = len(arr)
    total: int = (n + 1)*(n + 2)/2

    # casting needed because in python
    # the default here is float
    return int(total - sum(arr))