Missing Number

Concept

LeetCode #268.
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. You must implement a solution using only $O(1)$ extra space complexity and $O(n)$ runtime complexity.

Input: nums = [3,0,1]
Output: 2 (The array has length n=3. The range is [0, 1, 2, 3]. The number 2 is missing).

If we could use $O(N)$ space, we would just dump the array into a Hash Set and loop 0 to n to find the missing one.
Because we are restricted to $O(1)$ space, we have two legendary mathematical tricks available to us.

The Gauss Math Approach

Carl Friedrich Gauss famously discovered that the sum of all numbers from 0 to n can be calculated instantly using the formula:
Sum = n * (n + 1) / 2

If our array length is 3, the true mathematical sum of [0, 1, 2, 3] should be 3 * 4 / 2 = 6.
We loop through our actual array [3, 0, 1] and sum up the numbers. 3 + 0 + 1 = 4.
The True Sum minus our Actual Sum equals the missing number! 6 - 4 = 2.

This is an $O(N)$ time, $O(1)$ space masterpiece. However, it can suffer from Integer Overflow if the array is massive, because summing up millions of numbers might exceed the 32-bit maximum.

The XOR Approach

We can achieve the exact same result without any addition by using the magic property of XOR (^).

The Rule: X ^ X = 0
If you XOR a number against itself, it completely cancels out to 0.
XOR is also Commutative (order doesn’t matter). A ^ B ^ A = B. The As cancel each other out, leaving only B!

The Strategy:
We initialize a variable missing with the length of the array (n).
We loop through the array.
At every iteration, we XOR missing against the current Array Index, AND we XOR it against the current Array Value.

// Time Complexity: O(N)
// Space Complexity: O(1)

function missingNumber(nums: number[]): number {
    // Initialize with 'n', because the loop indices only go up to n-1!
    let missing = nums.length; 

    for (let i = 0; i < nums.length; i++) {
        // XOR the Index AND the Value
        missing = missing ^ i ^ nums[i];
    }

    return missing;
}

Let’s trace nums = [3, 0, 1]. Length is 3. missing = 3.

• i = 0, val = 3. missing = 3 ^ 0 ^ 3. (The 3s cancel! missing = 0).
• i = 1, val = 0. missing = 0 ^ 1 ^ 0. (The 0s cancel! missing = 1).
• i = 2, val = 1. missing = 1 ^ 2 ^ 1. (The 1s cancel! missing = 2).

The loop finishes. What is left in missing? 2. It is flawlessly correct, and immune to integer overflow!

Interview Questions

Q: A developer uses the .reduce() method to sum the array for the Gauss approach: let actualSum = nums.reduce((a, b) => a + b). Is this optimal?
A: Functionally it is correct and runs in $O(N)$ time. However, in JavaScript, array methods like .reduce and .forEach carry noticeable constant-time function call overhead compared to a raw for loop. For millions of elements, a standard for loop will execute significantly faster in V8.

Q: Why does the XOR trick not suffer from Integer Overflow like the Gauss addition approach?
A: Addition accumulates value, causing the number to grow larger and larger until it hits the hardware ceiling. XOR does not accumulate magnitude. It simply flips bits 0 to 1 or 1 to 0 within the existing 32-bit width. A 32-bit integer XORed against another 32-bit integer will always strictly produce a 32-bit integer. It can never mathematically overflow.