Missing Number — Sum and XOR Tricks

The Missing Number problem gives you an array nums containing n distinct numbers in the range [0, n]. Exactly one number from that range is missing. Return the missing number. The follow-up is to do it in O(n) time and O(1) extra space.

The Problem

You receive nums of length n, holding n distinct integers from [0, n]. By pigeonhole, exactly one value is absent. Return it.

Example: nums = [3, 0, 1] returns 2.

Intuition

The straightforward solution is to put every value into a hash set, then iterate from 0 to n and return the first missing index. It is O(n) time but O(n) space, and that fails the follow-up constraint. Sorting also works in O(n log n) and modifies the input.

Two clean O(n)-time, O(1)-space approaches exist. The first uses the closed-form sum of 0 through n, which is n(n+1)/2. Subtract the actual sum of the array; the difference is the missing number.

The second approach uses XOR. XOR has two properties we need: x ^ x = 0 and x ^ 0 = x. If we XOR all numbers from 0 to n together with every element of the array, each present number cancels itself out and only the missing number remains.

In Java or C++, n * (n + 1) can overflow if n is close to INT_MAX. The XOR version never overflows because it does not carry, so it is the more defensive choice in fixed-width languages.

Explanation with Example

Take nums = [3, 0, 1], so n = 3 and the expected range is [0, 3]. The missing number is 2.

Using the sum approach: expected = 3 * 4 / 2 = 6, actual sum = 4, missing = 2.

Using XOR: seed with n = 3. XOR with index and value at each step: 3 ^ 0 ^ 3 ^ 1 ^ 0 ^ 2 ^ 1 = 2.

indices: 3 0 1 2   (we seed with n=3, then XOR 0,1,2)
values:    3 0 1
xor walk: 3 ^ 0=3 ^ 3=0 ^ 1=1 ^ 0=1 ^ 2=3 ^ 1=2
result -> 2

Code

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

class Solution {
    public int missingNumber(int[] nums) {
        int result = nums.length;
        for (int i = 0; i < nums.length; i++) {
            result ^= i ^ nums[i];
        }
        return result;
    }
}

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int result = nums.size();
        for (int i = 0; i < (int)nums.size(); i++) {
            result ^= i ^ nums[i];
        }
        return result;
    }
};

Edge Cases

• If nums is empty, then n = 0 and the only number in the range [0, 0] is 0, so we should return 0. Both formulas handle that.
• If the missing number is 0 itself, the sum trick still works because the array sum will be exactly n(n+1)/2 - 0.
• If the missing number is n, the array contains 0 through n-1, again covered.
• In fixed-width integer languages, watch for overflow with the sum approach when n is large.

Complexity Analysis

All three optimal variants run in O(n) time. The hash-set version uses O(n) extra space. Both the sum and XOR versions use O(1) extra space, which is what the follow-up asks for.

The XOR version has the slight advantage of being branch-free and overflow-proof. The sum version is easier to read and more familiar to most reviewers. Pick the one you can defend most clearly.

How to Explain It in an Interview

Start by stating the pigeonhole observation: n values in [0, n] means exactly one is missing. Mention the hash-set solution first, note that it violates the space follow-up, and then offer the sum trick. Write it, then volunteer the XOR alternative as a way to dodge integer overflow. That sequence shows breadth without rambling.

If the interviewer asks how you would adapt this to two missing numbers, you can mention that XOR partitions the missing pair by a set bit — a clean transition into Single Number III.

Related Problems

• Single Number — pure XOR cancellation.
• Single Number III — two missing numbers via XOR partitioning.
• First Missing Positive — same flavor, harder because the range is unknown.
• Find All Numbers Disappeared in an Array — generalization with multiple missing values.