LC268-Missing-Number.py

"""
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?


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.

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


Constraints:
(*) n == nums.length
(*) 1 <= n <= 10^4
(*) 0 <= nums[i] <= n
(*) All the numbers of nums are unique.
"""
from typing import List


class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        """
        Runtime complexity: O(n)
        Space complexity: O(1)
        """
        n_numbers = len(nums)
        shift = n_numbers + 1
        # note if all numbers between 0 and len(nums) - 1 are present
        # change the sign if the number is present
        for i in range(n_numbers):
            n = nums[i] % shift
            if n < n_numbers:
                nums[n] += shift

        for i in range(len(nums)):
            if nums[i] < shift:
                return i

        return len(nums)


if __name__ == '__main__':
    from run_tests import run_tests

    correct_answers = [
        [[3,0,1], 2],
        [[0, 1], 2],
        [[9,6,4,2,3,5,7,0,1], 8],
        [[0], 1]
    ]
    print(f'Running tests for missingNumber')
    run_tests(Solution().missingNumber, correct_answers)