Solutions

# Sort, hash set, expected sum difference, or bit manipulation (xor)
# bit    

# math / expected sum: O(n) time, O(1) space
def missingNumber(nums: list[int]) -> int:
    expected_sum = sum([n for n in range(len(nums)+1)])
    actual_sum = sum(nums)
    return expected_sum - actual_sum
    
# bit manipulation: O(n) time, O(1) space
def missingNumber(nums: list[int]) -> int:
    xor = 0
    for n in range(len(nums)+1):
        xor ^= n

    for n in nums:
        xor ^= n
    return xor

# sorting: O(n lg n) time, O(1) space
def missingNumber(nums: list[int]) -> int:
    n = len(nums)
    nums.sort()
    for i in range(n):
        if nums[i] != i:
            return i
    return n

# hash set: O(n) time, O(n) space
def missingNumber(nums: list[int]) -> int:
    num_set = set(nums)
    n = len(nums)
    for i in range(n + 1):
        if i not in num_set:
            return i