Problem Description

You are given an array nums that contains n distinct numbers. These numbers are all from the range [0, n], which means the complete range should have n+1 numbers total (from 0 to n inclusive).

Since the array only contains n numbers but the range has n+1 numbers, exactly one number from the range is missing from the array. Your task is to find and return that missing number.

For example:

• If nums = [3, 0, 1], the array has n = 3 numbers from the range [0, 3]. The complete range is {0, 1, 2, 3}. The missing number is 2.
• If nums = [0, 1], the array has n = 2 numbers from the range [0, 2]. The complete range is {0, 1, 2}. The missing number is 2.
• If nums = [9,6,4,2,3,5,7,0,1], the array has n = 9 numbers from the range [0, 9]. The missing number is 8.

The solution uses XOR bitwise operation to efficiently find the missing number. The key insight is that XOR has two useful properties:

• Any number XOR with 0 remains unchanged: x ^ 0 = x
• Any number XOR with itself equals 0: x ^ x = 0

By XORing all numbers in the array with all numbers in the complete range [0, n], every number that appears will cancel out (due to x ^ x = 0), leaving only the missing number.

Intuition

Let's think about this problem step by step. We have an array with n numbers, and we know these numbers should be from the range [0, n]. Since the range has n+1 numbers but our array only has n numbers, one is missing.

The naive approach would be to check each number from 0 to n to see which one is absent. But there's a more elegant way using the XOR operation.

Consider what happens if we had all the numbers from 0 to n, and then we also had a duplicate set of all numbers from 0 to n. If we XOR all these numbers together, we'd get 0 because each number would appear twice, and x ^ x = 0.

Now, what if one number from the second set is missing? When we XOR everything, all pairs would cancel out to 0, except for the one number that doesn't have its pair - that's our missing number!

This is exactly our situation. We can think of it as:

• First set: the complete range [0, 1, 2, ..., n]
• Second set: our array nums (which is missing one number)

When we XOR all numbers from both sets, every number that exists in both will cancel out, leaving only the missing number.

In the code, enumerate(nums, 1) gives us indices starting from 1, so we're XORing:

• Indices: 1, 2, 3, ..., n (which covers part of our complete range)
• Array values: the n numbers from our array
• The index 0 is implicitly handled since we start from 1

Since XOR is commutative and associative, the order doesn't matter. All the numbers that appear in both the complete range and the array will cancel out, leaving us with the missing number.

Solution Approach

The solution implements the XOR bitwise operation approach to find the missing number efficiently.

The implementation uses Python's reduce function with the XOR operator to accumulate the result of XORing all elements. Here's how it works:

1. Enumerate with offset: enumerate(nums, 1) generates pairs of (index, value) where the index starts from 1 instead of 0. This means:

   • For an array like [3, 0, 1], we get pairs: (1, 3), (2, 0), (3, 1)

2. XOR each pair: For each pair (i, v), we compute i ^ v. This XORs the index with the corresponding array value.

3. Reduce with XOR: The reduce(xor, ...) function applies XOR cumulatively across all the i ^ v results. Since XOR is associative, this gives us:

   • (1 ^ nums[0]) ^ (2 ^ nums[1]) ^ (3 ^ nums[2]) ^ ...

Let's trace through why this works:

• We're XORing the indices [1, 2, 3, ..., n] with the array values
• The array contains all numbers from [0, n] except one
• After rearranging (since XOR is commutative), we're essentially XORing all numbers from 0 to n, where each appears once, except:
  • The missing number appears 0 times
  • The number 0 appears once (in the array but not in our indices since we start from 1)
  • The number at position of the missing value appears once (as an index)

Due to the XOR properties:

• Numbers that appear twice cancel out: x ^ x = 0
• The final result is the XOR of numbers appearing an odd number of times

The clever part is that by starting enumeration at 1, we ensure that the missing number will be the only one that appears an odd number of times in the overall XOR operation, making it the final result.

Time Complexity: O(n) - we traverse the array once Space Complexity: O(1) - only using a constant amount of extra space

Example Walkthrough

Let's walk through the solution with nums = [3, 0, 1]:

Step 1: Identify what we have

• Array: [3, 0, 1] with n = 3 numbers
• Complete range should be: [0, 1, 2, 3]
• Missing number: 2

Step 2: Set up enumeration Using enumerate(nums, 1), we get:

• (1, 3) → index 1, value 3
• (2, 0) → index 2, value 0
• (3, 1) → index 3, value 1

Step 3: XOR each pair For each pair (i, v), compute i ^ v:

• 1 ^ 3 = 2 (binary: 01 ^ 11 = 10)
• 2 ^ 0 = 2 (binary: 10 ^ 00 = 10)
• 3 ^ 1 = 2 (binary: 11 ^ 01 = 10)

Step 4: Reduce with XOR Now XOR all these results together:

• First: 2
• Then: 2 ^ 2 = 0
• Finally: 0 ^ 2 = 2

Result: 2 (our missing number!)

Why this works: Let's rearrange to see the cancellations more clearly. We're effectively XORing:

• From indices: 1, 2, 3
• From array: 3, 0, 1

Rearranging (since XOR is commutative):

• 0 ^ 1 ^ 2 ^ 3 (complete range)
• ^ 3 ^ 0 ^ 1 (array values)

Which becomes:

• (0 ^ 0) ^ (1 ^ 1) ^ 2 ^ (3 ^ 3)
• = 0 ^ 0 ^ 2 ^ 0
• = 2

Every number except 2 appears twice and cancels out, leaving us with the missing number!

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. This is because the code iterates through all elements in the nums array exactly once using enumerate(), and for each element, it performs a constant-time XOR operation. The reduce() function applies the XOR operation sequentially across all generated values, resulting in a linear pass through the data.

The space complexity is O(1). Despite using a generator expression (i ^ v for i, v in enumerate(nums, 1)), which is lazily evaluated, the reduce() function only maintains a single accumulator value at any given time. The generator doesn't create an intermediate list or array; it yields values one at a time. Therefore, the space usage remains constant regardless of the input size.

Common Pitfalls

Pitfall 1: Misunderstanding the Enumeration Starting Point

The Problem: A common mistake is to use enumerate(nums) (starting from 0) instead of enumerate(nums, 1). This would cause the solution to fail because we wouldn't be XORing with the complete range [0, n].

Incorrect Implementation:

# WRONG - starts enumeration from 0
return reduce(xor, (index ^ value for index, value in enumerate(nums)))

For nums = [3, 0, 1], this would compute:

• (0 ^ 3) ^ (1 ^ 0) ^ (2 ^ 1) = 3 ^ 1 ^ 3 = 1 (incorrect, should be 2)

Correct Implementation:

# CORRECT - starts enumeration from 1
return reduce(xor, (index ^ value for index, value in enumerate(nums, 1)))

This correctly computes:

• (1 ^ 3) ^ (2 ^ 0) ^ (3 ^ 1) = 2 (correct answer)

Pitfall 2: Not Including All Numbers in Range [0, n]

The Problem: Some might try to XOR only the array elements without considering the indices, or forget to include the number n in the XOR operation.

Incorrect Approach:

# WRONG - only XORs array elements
result = 0
for num in nums:
    result ^= num
# This doesn't help find the missing number

Correct Approach: The solution must XOR both the existing numbers AND the complete range [0, n]. By using enumerate(nums, 1), we ensure indices go from 1 to n, and when combined with array values (which contain n numbers from [0, n]), we effectively XOR with all numbers from 0 to n.

Pitfall 3: Alternative Correct Solution Not Recognized

The Confusion: The given solution might seem unintuitive. A clearer alternative that achieves the same result:

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

This explicitly shows we're XORing:

• All indices from 0 to n-1 (through enumerate)
• All values in the array
• The number n (initial value)

Together, this covers the complete range [0, n], making the logic more transparent.