You are given an array of length n containing n distinct numbers taken from the range 0 to n. Since the array has n distinct numbers and the numbers are in the range 0 to n, there is exactly one number missing.

Find the missing number.

Function Signature:

from typing import List

def find_missing_number(nums: List[int]) -> int:
    """
    Find the missing number in the array.

    Parameters:
    - nums: List of distinct numbers from 0 to n with one missing number.

    Returns:
    - int: The missing number.
    """
    # Your code here

Example:

# Input: nums = [3, 0, 1]
# Output: 2
# Explanation: The length of the array is 3, the range is 0-3. The missing number is 2.

# Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
# Output: 8
# Explanation: The length of the array is 9, the range is 0-9. The missing number is 8.

# Input: nums = [0]
# Output: 1
# Explanation: The length of the array is 1, the range is 0-1. The missing number is 1.

Note:

  • Your algorithm should run in linear runtime complexity.

Instructions:

  • Write the find_missing_number function to solve the problem using cyclic sort.
  • Implement your solution in Python.
  • Provide clear comments in your code.
  • Discuss the time and space complexity of your solution.

As always, we’ll share our solution to this problem tomorrow. Stay tuned 😊