Missing Number

Problem Statement

Given an array nums containing n integers in the range [0, n] without any duplicates, return the single number in the range that is missing from nums.

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

Example 1:

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

Example 2:

# Input: nums = [0,2]
# Output: 1

Constraints:

• 1 <= nums.length <= 1000

Recommended Time and Space Complexity

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

Consider the properties of the numbers in the array. They are in the range [0, n].

Hint 2

Think about using bitwise XOR to solve this problem with O(1) space complexity.

Hint 3

Alternatively, you can use the sum of numbers from 0 to n to find the missing number.

Solution

Sorting

def missing_number(nums: list[int]) -> int:
    n = len(nums)
    nums.sort()
    for i in range(n):
        if nums[i] != i:
            return i
    return n

Time complexity: O(n log n) Space complexity: O(1) or O(n) depending on the sorting algorithm.