Missing Number

Difficulty: Easy Source: NeetCode

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

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

Example 3: Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1] Output: 8

Constraints:

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

Follow up: Can you implement a solution using only O(1) extra space and O(n) time?

Prerequisites

Before attempting this problem, you should be comfortable with:

• Gaussian sum formula — the sum of integers from 0 to n is n * (n + 1) / 2
• XOR properties — a ^ a = 0, a ^ 0 = a, XOR is commutative and associative

1. Math — Gauss Sum

Intuition

If all numbers from 0 to n were present, their sum would be exactly n * (n + 1) / 2. We can compute the actual sum of the array. The difference is the missing number — it’s the only one that didn’t contribute to the total.

For [3, 0, 1] where n = 3:

• Expected sum: 3 * 4 / 2 = 6
• Actual sum: 3 + 0 + 1 = 4
• Missing: 6 - 4 = 2

Clean and simple, no extra data structures needed.

Algorithm

1. Let n = len(nums).
2. Compute expected = n * (n + 1) // 2.
3. Return expected - sum(nums).

Solution

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)


print(missingNumber([3, 0, 1]))              # 2
print(missingNumber([0, 1]))                 # 2
print(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # 8
print(missingNumber([0]))                    # 1

Complexity

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

2. XOR Bit Trick

Intuition

This is the same XOR cancellation idea from Single Number. If we XOR all the indices (0 through n) together with all the values in the array, every number that appears in both cancels out (a ^ a = 0). The only number that doesn’t appear in both is the missing one — it remains.

For [3, 0, 1] where n = 3:

indices XOR values
= (0 ^ 1 ^ 2 ^ 3) ^ (3 ^ 0 ^ 1)
= 0 ^ (1 ^ 1) ^ (3 ^ 3) ^ 2 ^ 0
= 0 ^ 0 ^ 0 ^ 2 ^ 0
= 2

The index 2 appears in the index list but not in the values list, so it survives.

In binary, 2 = 10. Every other number paired up and cancelled.

Algorithm

1. Initialize result = len(nums) (start with n, the index that has no paired value).
2. For each i from 0 to len(nums) - 1:
   • XOR result with both i and nums[i].
3. Return result.

Solution

def missingNumber(nums):
    result = len(nums)
    for i, num in enumerate(nums):
        result ^= i ^ num
    return result


print(missingNumber([3, 0, 1]))                     # 2
print(missingNumber([0, 1]))                         # 2
print(missingNumber([9, 6, 4, 2, 3, 5, 7, 0, 1]))  # 8
print(missingNumber([0]))                            # 1

Complexity

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

Common Pitfalls

Forgetting to include n in the XOR. The index list goes from 0 to n, but enumerate only gives you 0 to n-1. Starting result = len(nums) (which equals n) covers that last index, ensuring the XOR covers all values from 0 to n.

Integer overflow in other languages. In Java or C++, the Gauss sum n * (n + 1) / 2 can overflow a 32-bit int for large n. Python’s integers are arbitrary precision so this isn’t a concern here, but it matters if you’re translating the solution.

Trying to use sorting. Sorting works (O(n log n)) but it’s slower and misses the point of the problem. The math and XOR approaches are both O(n) with O(1) space, which is what the follow-up asks for.