Input: nums = [3, 0, 1]
Output: 2
Explanation: n = 3 since there are 3 numbers, so the range is [0,3]. 2 is the missing number.

Input: nums = [0, 1]
Output: 2
Explanation: n = 2 since there are 2 numbers, so the range is [0,2]. 2 is the missing number.

Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Explanation: n = 9 since there are 9 numbers, so the range is [0,9]. 8 is the missing number.

Input: nums = [0]
Output: 1
Explanation: n = 1 since there is 1 number, so the range is [0,1]. 1 is the missing number.

from typing import List

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        # Your code here
        pass

Solution Explanation & Interview Strategy

Approach 1: Summation (Gauss's Formula)

The sum of the first k non-negative integers (0 to k-1) is (k-1)*k/2. In our case, the numbers are from 0 to n (inclusive), where n is also the length of the input array nums. So, the complete sequence has n+1 numbers. The largest number in this complete sequence is n. The sum of integers from 0 to n is given by the formula n * (n + 1) / 2. We can calculate this expected sum. Then, we calculate the actual sum of elements in the given nums array. The difference between the expected sum and the actual sum will be the missing number.

from typing import List

class Solution:
    def missingNumber_summation(self, nums: List[int]) -> int:
        n_val = len(nums) # This is the 'n' from the range 0...n
        
        # Calculate the expected sum of numbers from 0 to n_val
        expected_sum = n_val * (n_val + 1) // 2 
        
        # Calculate the actual sum of numbers in the array
        actual_sum = sum(nums)
        
        return expected_sum - actual_sum

# Example Usage:
# sol = Solution()
# print(sol.missingNumber_summation([3, 0, 1]))  # Output: 2
# print(sol.missingNumber_summation([0, 1]))    # Output: 2

Approach 2: Bitwise XOR

The XOR operation has useful properties: x ^ x = 0 and x ^ 0 = x. Also, XOR is commutative and associative. We can XOR all numbers from 0 to n (where n = len(nums)). Let this be xor_all. Then, we XOR all numbers in the input array nums. Let this be xor_nums. The missing number will be xor_all ^ xor_nums. This is because all numbers present in both sequences will cancel each other out (x ^ x = 0), leaving only the missing number XORed with 0, which is the missing number itself.

from typing import List

class Solution:
    def missingNumber_xor(self, nums: List[int]) -> int:
        n_val = len(nums)
        missing = n_val # Start with n, as it's part of the 0..n range
        
        for i in range(n_val):
            missing ^= i       # XOR with the expected number at this index (0 to n-1)
            missing ^= nums[i] # XOR with the actual number in the array
            
        return missing

# Example Usage:
# sol = Solution()
# print(sol.missingNumber_xor([3, 0, 1]))  # Output: 2

Approach 3: Sorting

If we sort the array nums, the elements should ideally match their indices (i.e., nums[i] == i). If we find an index i where nums[i] != i, then i is the missing number. If the entire array matches its indices up to n-1, then the missing number must be n.

from typing import List

class Solution:
    def missingNumber_sorting(self, nums: List[int]) -> int:
        nums.sort() # Sort the array in-place
        n_val = len(nums)
        
        # Check if elements match their indices
        for i in range(n_val):
            if nums[i] != i:
                return i
        
        # If all elements from 0 to n-1 are present, then n is the missing number
        return n_val

# Example Usage:
# sol = Solution()
# print(sol.missingNumber_sorting([3, 0, 1]))  # Output: 2
# print(sol.missingNumber_sorting([0]))      # Output: 1

Approach 4: Using a Hash Set

We can insert all numbers from nums into a hash set for O(1) average time lookups. Then, iterate from 0 to n (inclusive) and check if each number is present in the hash set. The first number not found is the missing one.

from typing import List

class Solution:
    def missingNumber_hash_set(self, nums: List[int]) -> int:
        num_set = set(nums)
        n_val = len(nums)
        
        for number in range(n_val + 1): # Check numbers from 0 to n_val
            if number not in num_set:
                return number
        return -1 # Should not be reached given problem constraints