Missing Number
Problem
Given an array nums of n distinct numbers drawn from 0..n with exactly one omission, return the missing one.
XOR has two handy properties: x ^ x = 0 and x ^ 0 = x. Start with n and XOR every index i together with every value nums[i]. Every present number appears twice (as an index and a value) and cancels — only the missing value survives.
nums = [3, 0, 1]2def missing_number(nums):
x = len(nums)
for i, v in enumerate(nums):
x ^= i ^ v
return xfunction missingNumber(nums) {
let x = nums.length;
for (let i = 0; i < nums.length; i++) x ^= i ^ nums[i];
return x;
}class Solution {
public int missingNumber(int[] nums) {
int x = nums.length;
for (int i = 0; i < nums.length; i++) x ^= i ^ nums[i];
return x;
}
}int missingNumber(vector<int>& nums) {
int x = nums.size();
for (int i = 0; i < (int)nums.size(); i++) x ^= i ^ nums[i];
return x;
}Explanation
The numbers should be a full set 0..n but one is missing. We find it with XOR, leaning on two rules: x ^ x = 0 and x ^ 0 = x. If we XOR together all the indices and all the values, every number that is present shows up twice and cancels.
We seed x with n (the array length), which stands in for the index n that has no matching slot. Then for each position we fold in both the index i and the value nums[i] with x ^= i ^ nums[i].
Across the whole run, every number from 0 to n appears as an index, and every present number also appears as a value. Pairs cancel to zero, so the single number that never appears as a value is the lone survivor in x.
Example: nums = [3, 0, 1], so n = 3. Start x = 3, then fold in indices 0,1,2 and values 3,0,1. The 0, 1, and 3 all cancel, leaving x = 2, the missing number.
This needs only one integer of extra space and a single pass through the array.