Missing Number

Problem

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.

Constraints:

n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
All the numbers of nums are unique.

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

Solution

Approach 1: XOR Bit Manipulation

The key insight is that XOR-ing a number with itself gives 0, and XOR-ing with 0 gives the number. XOR all indices and all values - the missing number will remain.

Implementation

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        result = len(nums)  # Start with n
        for i in range(len(nums)):
            result ^= i ^ nums[i]
        return result

Approach 2: Gauss Formula (Sum)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        # Sum of 0 to n
        expected_sum = n * (n + 1) // 2
        actual_sum = sum(nums)
        return expected_sum - actual_sum

Approach 3: Hash Set (Not Optimal Space)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        num_set = set(nums)
        for i in range(len(nums) + 1):
            if i not in num_set:
                return i

Approach 4: Sort and Linear Search (Not Optimal Time)

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        nums.sort()

        # Check if 0 is missing
        if nums[0] != 0:
            return 0

        # Check if n is missing
        if nums[-1] != len(nums):
            return len(nums)

        # Find the gap
        for i in range(1, len(nums)):
            if nums[i] != nums[i - 1] + 1:
                return nums[i - 1] + 1

Complexity Analysis

XOR Approach:

Time Complexity: O(n), single pass through array.
Space Complexity: O(1), only using one variable.

Sum Approach:

Time Complexity: O(n)
Space Complexity: O(1)

Hash Set Approach:

Time Complexity: O(n)
Space Complexity: O(n) for the set.

Sort Approach:

Time Complexity: O(n log n) for sorting
Space Complexity: O(1) or O(n) depending on sorting implementation

Key Insights

XOR Properties: XOR-ing all numbers from 0 to n with all numbers in array cancels out present numbers, leaving missing one.
Mathematical Formula: Sum of 0 to n is n*(n+1)/2. Subtract actual sum to find missing number.
XOR Cancellation: For complete array: 0^1^2^…^n ^ 0^1^2^…^n = 0. With missing number, result is the missing number.
Space-Time Tradeoff: Hash set uses O(n) space for O(n) time. XOR and sum use O(1) space for O(n) time.
Integer Overflow: In some languages, sum approach might overflow for large n. XOR doesn’t have this issue.
Optimal Solutions: Both XOR and sum approaches achieve O(n) time and O(1) space.
XOR Trick: result = n ^ (0^nums[0]) ^ (1^nums[1]) ^ ... ^ ((n-1)^nums[n-1]) simplifies to missing number.