268. Missing Number.py

"""
https://leetcode.com/problems/missing-number/

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.

Example 1:
    Input: nums = [3,0,1]
    Output: 2
    Explanation: n = 3 since there are 3 numbers, so all numbers are in the range [0,3].
    2 is the missing number in the range since it does not appear in nums.

Example 2:
    Input: nums = [0,1]
    Output: 2
    Explanation: n = 2 since there are 2 numbers, so all numbers are in the range [0,2].
    2 is the missing number in the range since it does not appear in nums.

Example 3:
    Input: nums = [9,6,4,2,3,5,7,0,1]
    Output: 8
    Explanation: n = 9 since there are 9 numbers, so all numbers are in the range [0,9].
    8 is the missing number in the range since it does not appear in nums.

"""


class Solution(object):
    """

    Time: O(n) (нахождение суммы)
    Space: O(1)

    """
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        total_sum = (n * (n + 1)) / 2
        nums_sum = sum(nums)

        return total_sum - nums_sum


solution = Solution()

assert solution.missingNumber([3, 0, 1]) == 2
assert solution.missingNumber([0, 1]) == 2
assert solution.missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]) == 8