3
xor
Given an array holding a permutation of 0..n with exactly one value absent, find it in O(n) time and O(1) space using XOR bit manipulation — pair every index with its value and let the un-matched number survive.
You receive an array of n distinct integers drawn from 0..n — exactly one value is missing. Return it.
Example: nums = [3, 0, 1] — the range is 0..3 but 2 is absent → return 2. You can't simply sort and scan (that's O(n log n)); you need a single pass.
a ^ a = 0 and a ^ 0 = a. If you XOR together all indices 0..n and all values in the array, every present number appears exactly twice (once as an index, once as a value) and cancels out. The one missing number has no partner — it survives as the final result.0..n but the loop only reaches indices 0..n-1, so seed with xor = n to include the top bound.xor ^= i ^ nums[i] — folds in the index and the value simultaneously.nums has been XOR-ed in twice (once as an index, once as itself) and cancelled. Only the missing value has no partner.xor = 0 and only loop over the values, forgetting to include the indices 0..n. The pairing only works when every expected number appears on both sides — index side and value side. Seed with n and fold in i alongside nums[i].The Gauss sum alternative: the sum of 0..n is n*(n+1)/2. Subtract the actual array sum — the difference is the missing number. Both approaches are O(n) / O(1), but XOR avoids any risk of integer overflow on very large n.
3 elements so the full range is 0..3. Seed xor = n = 3. XOR-ing a number with itself cancels to 0; the lone survivor will be the missing value.function missingNumber(nums: number[]): number {
// XOR approach — O(n) time, O(1) space
let xor = nums.length; // seed with n (the "extra" index)
for (let i = 0; i < nums.length; i++) {
xor ^= i ^ nums[i]; // fold in index i and value nums[i]
}
return xor; // every paired value cancelled; survivor is missing
}
// Alternative: Gauss sum — O(n) time, O(1) space
// function missingNumber(nums: number[]): number {
// const n = nums.length;
// const expected = (n * (n + 1)) / 2; // sum of 0..n
// const actual = nums.reduce((a, b) => a + b, 0);
// return expected - actual;
// }0 to n-1, producing indices 0..n-1. But the expected range is 0..n. Seeding xor = n injects the top bound so every expected index is accounted for.xor ^= i ^ nums[i]. This is equivalent to XOR-ing the two sets {0,1,...,n} and {nums[0],...,nums[n-1]} together in one loop. Every present value appears once in each set → pairs cancel to 0.xor. This is the answer.expected = n*(n+1)/2 then subtract the array sum. Same O(n) / O(1) complexity, but relies on subtraction which could overflow for very large inputs in a language without big integers. XOR is always safe.xor. The Gauss formula is the same complexity; XOR wins on overflow safety.a ^ a = 0 and a ^ 0 = a so the interviewer sees you understand why it works.n*(n+1)/2 can overflow a 32-bit integer for large n. XOR never overflows. In TypeScript numbers are 64-bit floats (safe up to 2^53) so both are fine in practice, but it's a good point to raise.nums = [0] → missing is 1; nums = [1] → missing is 0. Both work correctly because we seed with n = 1.| "missing one value from 0..n" | XOR index ^ value, seed = n |
| "find unpaired / single element" | XOR — pairs cancel to 0 |
| "O(1) space, no sorting" | Bit manipulation or Gauss sum |
| "sum of consecutive integers" | n*(n+1)/2 Gauss formula |
function missingNumber(nums: number[]): number {
let xor = nums.length;
for (let i = 0; i < nums.length; i++) {
xor ^= i ^ nums[i];
}
return xor;
}a ^ a = 0. Every present value appears twice (once as an index, once as a value) and cancels. The missing value has no partner — it survives.nums = [3, 0, 1]. What does the XOR approach return?nums = [1]. What is the missing number?