Back to solutions

Missing Number

EasyBit Manipulation

An array contains n distinct numbers from the range [0, n]. Return the one number in the range that is missing.

Open problem
Constraints
  • 1 <= n <= 10^4
  • All numbers are distinct

XOR of indices and values

Time O(n)Space O(1)

XOR every index 0..n with every value. Pairs that appear in both cancel out, leaving only the missing index. This avoids overflow and uses no extra space.

#include <bits/stdc++.h>
using namespace std;

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