"""
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

Follow up: Could you implement a solution using only O(1) extra space complexity and O(n) runtime complexity?
"""

# class Solution:
#     def missingNumber(self, nums: List[int]) -> int:
#         original_sum = sum([i for i in range(len(nums)+1)])
#         return original_sum - sum(nums)

class Solution:
    def missingNumber(self, nums):
        nums.sort()

        # Ensure that n is at the last index
        if nums[-1] != len(nums):
            return len(nums)
        # Ensure that 0 is at the first index
        elif nums[0] != 0:
            return 0

        # If we get here, then the missing number is on the range (0, n)
        for i in range(1, len(nums)):
            expected_num = nums[i-1] + 1
            if nums[i] != expected_num:
                return expected_num


if __name__ == "__main__":
    nums = [4,5,6,7,0,1,2]
    
    print(Solution().missingNumber(nums))