#74 · Bit Manipulation

Missing Number

Given an array of n distinct numbers taken from the range 0 … n, return the one number in that range that is missing from the array.

EasyLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Arithmetic series

The numbers 0 … n add up to n(n + 1)/2. The array holds all of them except one, so the missing number is the expected sum minus the actual sum.

Memory layout

A single accumulator.

Operation	Cost
time / space	O(n) / O(1)

XOR as a cancelling accumulator

x ^ x = 0 and x ^ 0 = x, and XOR is commutative and associative. XOR-ing the full range with the array values cancels every present number and leaves the missing one, with no risk of overflow.

Memory layout

A single accumulator.

Operation	Cost
time / space	O(n) / O(1)

Why it fits

The set of possible numbers is known and complete, so only the difference between the full set and the array matters.
Both the sum and the XOR are order-independent summaries of a collection, and each can be compared with the same summary of the full range.
XOR has the advantage of never overflowing and of working for any cancelling structure, not just arithmetic.

Why alternatives degrade

Sorting then scanning for the first gap:: Correct but O(n log n); the known range makes sorting unnecessary.
Checking each candidate against the array:: O(n²): n + 1 candidates times a scan each.
Boolean presence array:: O(n) time but also O(n) extra memory, which the sum and XOR tricks avoid.

Four approaches, from naive to production

1 · beginner

Check every candidate by scanning

time O(n²)space O(1)

For each k from 0 to n, scan the whole array to see whether k appears. The first k that does not appear is the answer.

int missingNumber(vector<int>& nums) {
    for (int k = 0; k <= (int)nums.size(); k++) {
        bool found = false;
        for (int x : nums) {
            if (x == k) found = true;
        }
        if (!found) return k;
    }
    return -1;
}

public int missingNumber(int[] nums) {
    for (int k = 0; k <= nums.length; k++) {
        boolean found = false;
        for (int x : nums) {
            if (x == k) found = true;
        }
        if (!found) return k;
    }
    return -1;
}

def missing_number(nums):
    for k in range(len(nums) + 1):
        found = False
        for x in nums:
            if x == k: found = True
        if not found: return k
    return -1

function missingNumber(nums: number[]): number {
  for (let k = 0; k <= nums.length; k++) {
    let found = false;
    for (const x of nums) {
      if (x === k) found = true;
    }
    if (!found) return k;
  }
  return -1;
}

Flaws & bottlenecks

A full scan of the array for every candidate.
The inner loop does not stop early when it finds the value.
Quadratic: too slow for 10,000 or more elements.

Interviewer cross-questions

Why are there n + 1 candidates?

Say: The numbers come from 0 … n, which is n + 1 values, and the array holds n of them.

How can membership be made O(1)?

Say: Put the numbers in a hash set or a boolean array indexed by value.

Can you avoid storing anything?

Say: Yes: compare the sum or the XOR of the array with that of the full range.

2 · intermediate

Hash set membership

time O(n)space O(n)

Insert all numbers into a hash set, then check the candidates 0 … n in order and return the first one that is not in the set.

int missingNumber(vector<int>& nums) {
    unordered_set<int> seen(nums.begin(), nums.end());
    for (int k = 0; k <= (int)nums.size(); k++) {
        if (!seen.count(k)) return k;
    }
    return -1;
}

public int missingNumber(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) seen.add(x);
    for (int k = 0; k <= nums.length; k++) {
        if (!seen.contains(k)) return k;
    }
    return -1;
}

def missing_number(nums):
    seen = set(nums)
    for k in range(len(nums) + 1):
        if k not in seen: return k
    return -1

function missingNumber(nums: number[]): number {
  const seen = new Set<number>(nums);
  for (let k = 0; k <= nums.length; k++) {
    if (!seen.has(k)) return k;
  }
  return -1;
}

Flaws & bottlenecks

O(n) extra memory for the set.
Hashing integers is slower than plain arithmetic.
Does not use the fact that exactly one number is missing.

Interviewer cross-questions

What if the array might miss several numbers?

Say: The set (or a boolean array) approach generalises: collect every candidate not in the set. The sum and XOR tricks only work for exactly one missing number.

Could a boolean array replace the set?

Say: Yes: values are 0 … n, so an array of n + 1 flags is smaller and faster than a hash set.

What is the memory cost?

Say: About n entries in the set; the XOR or sum solutions use a single integer.

3 · advanced

Expected sum minus actual sum

time O(n)space O(1)

Compute n(n + 1)/2, the sum of 0 … n, add up the array, and subtract: the difference is the missing number.

int missingNumber(vector<int>& nums) {
    long long n = nums.size();
    long long sum = 0;
    for (int x : nums) sum += x;
    return (int)((n * (n + 1)) / 2 - sum);
}

public int missingNumber(int[] nums) {
    long n = nums.length;
    long sum = 0;
    for (int x : nums) sum += x;
    return (int) ((n * (n + 1)) / 2 - sum);
}

def missing_number(nums):
    n = len(nums)
    total = 0
    for x in nums: total += x
    return n * (n + 1) // 2 - total

function missingNumber(nums: number[]): number {
  const n = nums.length;
  let sum = 0;
  for (const x of nums) sum += x;
  return (n * (n + 1)) / 2 - sum;
}

Flaws & bottlenecks

The sum can overflow a 32-bit integer for large n (about n²/2); use a 64-bit type or subtract incrementally.
Works only when exactly one number is missing and the rest are distinct.
Division by 2 is exact only because n(n + 1) is always even.

Interviewer cross-questions

How do you avoid overflow?

Say: Use a 64-bit sum, or accumulate the difference as you go: start with n and add (i − nums[i]) for each i, which stays small.

What if a number is duplicated and one is missing?

Say: The sum then gives (missing − duplicate), which does not identify either. That variant needs another equation (sum of squares) or a different method such as XOR with a bit split.

Why is n(n + 1)/2 an integer?

Say: Of two consecutive integers one is even, so the product is even.

4 · expert

XOR of all indices and values

time O(n)space O(1)

Start with n and XOR in every index i and every value nums[i]. Equal numbers cancel in pairs, so only the missing number remains.

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

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

def missing_number(nums):
    acc = len(nums)
    for i in range(len(nums)):
        acc ^= i ^ nums[i]
    return acc

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

Flaws & bottlenecks

Less obvious than the sum formula, and the cancellation argument must be explained.
Still assumes exactly one missing number and no duplicates.
Correct only if the values really lie in 0 … n.

Interviewer cross-questions

Why does the XOR leave the missing number?

Say: XOR over 0 … n includes every number once; XOR over the array includes every number except the missing one once. Combined, each present number appears twice and cancels; the missing one appears once.

Why start with n?

Say: The loop XORs the indices 0 … n − 1. The index n is not covered by the loop, so n is XORed in at the start.

Why prefer XOR to the sum?

Say: XOR cannot overflow and uses no arithmetic. The same idea works for finding the single unpaired element in any collection (Single Number).

Synchronized code walkthrough

Showing: Check every candidate by scanning — shares the player above; click any step to jump.

int missingNumber(vector<int>& nums) {
    for (int k = 0; k <= (int)nums.size(); k++) {
        bool found = false;
        for (int x : nums) {
            if (x == k) found = true;
        }
        if (!found) return k;
    }
    return -1;
}

public int missingNumber(int[] nums) {
    for (int k = 0; k <= nums.length; k++) {
        boolean found = false;
        for (int x : nums) {
            if (x == k) found = true;
        }
        if (!found) return k;
    }
    return -1;
}

def missing_number(nums):
    for k in range(len(nums) + 1):
        found = False
        for x in nums:
            if x == k: found = True
        if not found: return k
    return -1

function missingNumber(nums: number[]): number {
  for (let k = 0; k <= nums.length; k++) {
    let found = false;
    for (const x of nums) {
      if (x === k) found = true;
    }
    if (!found) return k;
  }
  return -1;
}

int missingNumber(vector<int>& nums) {
    unordered_set<int> seen(nums.begin(), nums.end());
    for (int k = 0; k <= (int)nums.size(); k++) {
        if (!seen.count(k)) return k;
    }
    return -1;
}

public int missingNumber(int[] nums) {
    Set<Integer> seen = new HashSet<>();
    for (int x : nums) seen.add(x);
    for (int k = 0; k <= nums.length; k++) {
        if (!seen.contains(k)) return k;
    }
    return -1;
}

def missing_number(nums):
    seen = set(nums)
    for k in range(len(nums) + 1):
        if k not in seen: return k
    return -1

function missingNumber(nums: number[]): number {
  const seen = new Set<number>(nums);
  for (let k = 0; k <= nums.length; k++) {
    if (!seen.has(k)) return k;
  }
  return -1;
}

int missingNumber(vector<int>& nums) {
    long long n = nums.size();
    long long sum = 0;
    for (int x : nums) sum += x;
    return (int)((n * (n + 1)) / 2 - sum);
}

public int missingNumber(int[] nums) {
    long n = nums.length;
    long sum = 0;
    for (int x : nums) sum += x;
    return (int) ((n * (n + 1)) / 2 - sum);
}

def missing_number(nums):
    n = len(nums)
    total = 0
    for x in nums: total += x
    return n * (n + 1) // 2 - total

function missingNumber(nums: number[]): number {
  const n = nums.length;
  let sum = 0;
  for (const x of nums) sum += x;
  return (n * (n + 1)) / 2 - sum;
}

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

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

def missing_number(nums):
    acc = len(nums)
    for i in range(len(nums)):
        acc ^= i ^ nums[i]
    return acc

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