Missing Number

Approach Summary

XOR of all indices (0..n) XOR all array values. The missing number is what remains. Or use Gauss sum formula.

Full Solution & Approach

XOR is the clean O(1)-space solution. XOR every index with every value and also XOR in n. Since a ^ a = 0, every value that exists in the array cancels with its index, leaving only the index — the number — that never appeared. Concretely, result starts as n (the missing number must lie in [0, n]), then result ^= i ^ nums[i] for every i. Pairs where nums[i] === i cancel out entirely; the missing value has no counterpart, so it survives. Alternative solutions: sort and scan (O(n log n)), the sum formula (risky overflow for huge n), or a boolean array (O(n) space). The XOR version is optimal in both time and space and generalizes to other find-the-odd-one-out problems.

Single pass with constant-time XOR per element — O(n) time and O(1) space.

Solution Code

Solution

def missing_number(nums: list[int]) -> int:
    result = len(nums)
    for i, n in enumerate(nums):
        result ^= i ^ n
    return result

function missingNumber(nums) {
  let result = nums.length;
  for (let i = 0; i < nums.length; i++) {
    result ^= i ^ nums[i];
  }
  return result;
}

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

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

Edge Cases to Watch

Missing number is 0 — XOR handles it since 0 is its own identity
Missing number is n (the largest) — the result initialized to n catches it
Single element [0] — missing is 1; [1] — missing is 0

How to Recognize This Pattern

Find missing number in 0..n
XOR or math sum

Complexity Analysis

Time Complexity

O(n)

Space Complexity

O(1)