Missing Number

Problem Description

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.

Examples

Constraints

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

XORing Identical Values to Cancel Out Pairs

There are two optimal ways to solve this in O(n) time and O(1) space:

1. Arithmetic Sum (Gauss Formula): The sum of numbers from 0 to n is n * (n + 1) / 2. If we sum all elements in nums and subtract this from the expected total sum, the difference is the missing number.
2. Bitwise XOR: The XOR operator has a property: x ^ x = 0. If we XOR all indices from 0 to n and all values in nums together, matching numbers will cancel each other out to 0, leaving only the missing number as the result.

The XOR method is safer because it avoids integer overflow when n is extremely large.

Solution 1: Arithmetic Sum (Gauss Formula)

Calculate the expected sum of 0 to n and subtract the actual sum of the array.

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : nums) {
            actualSum += num;
        }
        return expectedSum - actualSum;
    }
}

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

#include <vector>
#include <numeric>

class Solution {
public:
    int missingNumber(std::vector<int>& nums) {
        int n = nums.size();
        int expectedSum = n * (n + 1) / 2;
        int actualSum = std::accumulate(nums.begin(), nums.end(), 0);
        return expectedSum - actualSum;
    }
};

Complexity Analysis:

• Time Complexity: O(n). We sum the array once.
• Space Complexity: O(1) auxiliary space.

Where it breaks: If n is extremely large (e.g. 10⁵), the multiplication n * (n + 1) can overflow a standard 32-bit signed integer. The constraints state n <= 10⁴, meaning values stay within integer limits. For larger ranges, use the XOR approach.

Solution 2: Bitwise XOR (No Overflow Risk)

XOR all indices and elements together. The duplicate values cancel out, leaving the missing number.

class Solution {
    public int missingNumber(int[] nums) {
        int result = nums.length; // start with index n
        for (int i = 0; i < nums.length; i++) {
            result ^= i ^ nums[i]; // XOR index and value
        }
        return result;
    }
}

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        result = len(nums)  # start with index n
        for i in range(len(nums)):
            result ^= i ^ nums[i]  # XOR index and value
        return result

#include <vector>

class Solution {
public:
    int missingNumber(std::vector<int>& nums) {
        int result = nums.size(); // start with index n
        for (int i = 0; i < nums.size(); i++) {
            result ^= i ^ nums[i]; // XOR index and value
        }
        return result;
    }
};

Complexity Analysis:

• Time Complexity: O(n). Single pass.
• Space Complexity: O(1) auxiliary space.

Where it breaks: Nothing breaks. It runs correctly without any overflow risks.

Common Mistakes

• Forgetting to include index n in the XOR or Sum. The range of values is [0, n], meaning there are n + 1 possible values. The loop index only goes up to n - 1, so you must initialize result = n (or add n to the sum) to include it.
• Using an O(n) hash set to lookup elements. Creating a set of elements and checking set.contains(i) for each index takes O(n) space. While it runs in O(n) time, it violates the constant space expectation.
• Integer overflow in the sum multiplication. If you write the formula in Java as n * (n + 1) / 2, convert to long if n can be large.

Frequently Asked Questions

Why does the XOR method work? XOR is commutative and associative, meaning order does not matter: a ^ b ^ a = b. Since all numbers in [0, n] are present in either the indices or the elements, the missing number appears only once, while all other numbers appear exactly twice (once as an index, once as an element), cancelling each other out.

How does this change if there are multiple missing numbers? If there are multiple missing numbers, the sum or XOR values will represent the merged state of all missing elements, and you cannot identify them individually without extra space.

What does this problem test in interviews? It tests your ability to optimize math calculations, apply properties of the XOR bitwise operator, and avoid integer overflows.

← All Problems