Find the Missing Number [Solution]

Here’s a Python implementation of the find_missing_number function using cyclic sort:

from typing import List

def find_missing_number(nums: List[int]) -> int:
    n = len(nums)

    # Perform cyclic sort
    i = 0
    while i < n:
        if 0 <= nums[i] < n and nums[i] != nums[nums[i]]:
            nums[nums[i]], nums[i] = nums[i], nums[nums[i]]
        else:
            i += 1

    # Find the missing number
    for i in range(n):
        if nums[i] != i:
            return i

    # If no missing number found, return the next number
    return n

# Example usage:
result1 = find_missing_number([3, 0, 1])
print(result1)  # Output: 2

result2 = find_missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1])
print(result2)  # Output: 8

result3 = find_missing_number([0])
print(result3)  # Output: 1

This solution uses the cyclic sort algorithm to rearrange the numbers in the array. The missing number can be determined by finding the first position where the value does not match the index.

Time Complexity:

The time complexity of the algorithm is O(n), where n is the length of the array.

Space Complexity:

The space complexity is O(1).