Missing Number — XOR Cancellation vs Gauss Sum Formula

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. The constraints suggest you implement a solution that uses only constant extra space and runs in linear time.

Constraints:

• 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, all in [0..3]. 2 is missing.

Example 2:

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

Example 3:

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

Why This Problem Matters#

Missing Number is a classic interview "warm-up" that lets candidates demonstrate two completely different bit-and-math techniques on the same problem. The XOR solution showcases bitwise cancellation; the Gauss formula showcases arithmetic identity. Top tech companies (Amazon, Google, Microsoft) often follow up with overflow-related questions, which is why the XOR approach has a real practical advantage even though both are linear time.

The deeper lesson: complementary techniques can solve the same problem with very different trade-offs. XOR is overflow-safe and bit-friendly; arithmetic sums are easier to explain and generalize but can overflow on large inputs. Knowing both — and articulating when each is better — is exactly the depth FAANG interviewers expect.

The Core Insight#

Approach 1 — XOR cancellation. Recall that a ^ a = 0 and XOR is commutative and associative. If we XOR all indices [0, 1, 2, ..., n] together with all values in the array, every index that also appears as a value cancels itself out, leaving only the missing value:

result = (0 ^ 1 ^ 2 ^ ... ^ n)  XOR  (nums[0] ^ nums[1] ^ ... ^ nums[n-1])
       = missing_number

Concretely, you initialize result = n (which covers the index n that has no array slot) and XOR each i ^ nums[i] pair into it.

Approach 2 — Gauss arithmetic series. The expected sum of 0..n is n * (n + 1) / 2. Subtracting the actual array sum yields the missing value:

missing = n * (n + 1) / 2  -  sum(nums)

Both are O(n) time and O(1) space, but XOR avoids any risk of integer overflow with very large n while Gauss is conceptually simpler.

Visual Dry Run#

Input: nums = [3, 0, 1], n = 3

XOR approach:

Final result: 2. The pairs (0,3), (1,0), (2,1) cancel collectively, leaving the missing index 2.

Gauss approach:

expected = 3 * 4 / 2 = 6
actual   = 3 + 0 + 1 = 4
missing  = 6 - 4 = 2

Both approaches arrive at the answer in a single linear pass.

Solution (Optimal)#

Python#

class Solution:
    def missingNumber(self, nums: list[int]) -> int:
        # XOR approach: cancellation isolates the missing index
        # Start with n because index n has no corresponding nums[i]
        result = len(nums)
        for i, n in enumerate(nums):
            result ^= i ^ n   # pair each index with its value; duplicates cancel
        return result
 
class SolutionGauss:
    def missingNumber(self, nums: list[int]) -> int:
        # Arithmetic series: expected total minus observed total
        n = len(nums)
        return n * (n + 1) // 2 - sum(nums)

JavaScript#

var missingNumber = function(nums) {
    // XOR approach — overflow-safe and bit-friendly
    let result = nums.length;
    for (let i = 0; i < nums.length; i++) {
        result ^= i ^ nums[i];   // every present index cancels with its value
    }
    return result;
};
 
// Alternative Gauss formula:
// var missingNumber = nums => nums.length * (nums.length + 1) / 2
//                              - nums.reduce((a, b) => a + b, 0);

Complexity: Time O(n), Space O(1) for both approaches.

Common Mistakes#

1. Forgetting to seed XOR with n. Indices range over [0, n - 1] while values include n. If you XOR only indices and values, you miss accounting for the value n that may or may not be present. Initializing result = n cleanly handles this.

2. Integer overflow with the Gauss formula. For very large n (e.g., 10^9), n * (n + 1) may overflow 32-bit signed integers. Use 64-bit arithmetic or prefer the XOR approach.

3. Sorting and scanning in O(n log n). A correct but suboptimal approach: sort the array and find the first index where nums[i] != i. The interviewer wants linear time.

4. Using a hash set in O(n) space. Also correct but violates the implicit space constraint. The XOR or Gauss approaches achieve O(1) space.

5. Off-by-one in loop bounds. Iterating i over range(n + 1) and indexing nums[i] causes IndexError. The valid index loop is range(n); pair index n is handled by the initial result = n.

Interview Tips#

• Open by stating both approaches: "I see two clean linear solutions — XOR cancellation and the Gauss sum formula." This shows breadth.
• Pick XOR when overflow is a concern; mention that explicitly. Senior interviewers reward candidates who anticipate edge cases.
• For the Gauss approach, mention floating-point pitfalls if the interviewer suggests (n * (n + 1)) / 2 in a language without integer division. Always use // 2 or integer types.
• If pressed for an even more efficient pattern: note that on a CPU, the XOR approach has zero data dependencies between iterations and can be vectorized; the sum has the same property.

Follow-up Questions#

Q: What if there are two missing numbers? XOR all values and all indices to get a ^ b. Then apply the Single Number III partition trick to recover the two missing numbers individually.

Q: What if the array could contain duplicates? Both approaches break because duplicates change parity (XOR) and totals (Gauss). You'd need a frequency map or cycle-based detection like Floyd's algorithm.

Q: How would you handle an array stored on disk that you can only stream once? Both XOR and Gauss work — they only need running accumulators. Streaming is naturally O(1) memory.

Q: Why does XOR-cancellation work? XOR has the algebraic identity x ^ x = 0. Applying XOR to the multiset of all indices and all values, every present pair cancels. Only the missing index remains because nothing pairs with it.

Key Takeaways#

• XOR every index i with every value nums[i], seeding with n, to isolate the missing number via cancellation.
• The Gauss formula n * (n + 1) / 2 - sum(nums) is equally fast but vulnerable to integer overflow at scale.
• Both approaches run in O(n) time and O(1) space — choose XOR for overflow safety, Gauss for clarity.
• Avoid sorting (O(n log n)) and hash sets (O(n) space); they violate the optimal complexity targets.
• Initialize the XOR accumulator with n to account for the index that has no slot in the array.
• These two approaches together form a foundational pattern for "find the missing element" variants across interviews.