Problem Statement

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.

Additional information

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

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 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 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 since it does not appear in nums.

Bitwise XOR

Intuition

There are two common O(1) space approaches: Math (Summation) and Bitwise XOR. Since we are focusing on Bit Manipulation, we will use the XOR method, which is safe from integer overflow issues in other languages.

The XOR Strategy:

• We know the array should contain numbers from 0 to n.
• We have the actual numbers in nums.
• If we XOR all the numbers from 0 to n, and then XOR that result with all the numbers in nums, every number that appears in both sets will cancel out (become 0).
• The only number left will be the one that was missing.

Example:

• Range [0, 3]: 0 ^ 1 ^ 2 ^ 3
• Array [3, 0, 1]: 3 ^ 0 ^ 1
• Combined: (0^0) ^ (1^1) ^ (3^3) ^ 2
• Result: 2

Algorithm

Step 1: Initialize result equal to n (because the loop will only go up to n-1, we need to include n manually).

Step 2: Loop through the array using index i and value num.

Step 3: Update result by XORing it with the current index i and the current value num.

• result = result ^ i ^ num

Step 4: Return result.

def missing_number(nums: list[int]) -> int:
    n = len(nums)
    result = n
    
    for i in range(n):
        result ^= i ^ nums[i]
        
    return result

Time & Space Complexity

• Time Complexity: O(n). We iterate through the array once.
• Space Complexity: O(1). We use only one variable.