Difficulty: Easy Pattern: Bit Manipulation LeetCode: https://leetcode.com/problems/missing-number/
Given an array nums containing n distinct numbers taken from the
range [0, n] (inclusive), return the one number from that range that is
missing from the array.
Signature:
int missingNumber(int[] nums)
Examples:
Input: nums = [3,0,1]
Output: 2 # range [0,1,2,3]; 2 is absent
Input: nums = [0,1]
Output: 2 # range [0,1,2]; 2 is absent
Input: nums = [9,6,4,2,3,5,7,0,1]
Output: 8 # range [0..9]; 8 is absent
The trigger signal is “without extra space” combined with the “every value appears … except one” structure – the same shape as Single Number (LC 136), but now the duplicate is supplied by the index range itself.
The full set of values that should be present is {0, 1, 2, ..., n} –
exactly n + 1 values. The array holds n of them, so one is missing. If
we XOR together the desired set {0, 1, ..., n} and the actual array
contents, every value that appears in both cancels (x ^ x == 0), and the
one value that appears in the desired set but not the array survives
(0 ^ x == x). That survivor is the missing number.
The desired set {0, 1, ..., n} is conveniently produced by XOR-ing the
loop index i (which runs 0..n-1) together with n itself. So the scan
is: accumulate i ^ nums[i] for each index, seed the accumulator with n,
and whatever is left at the end is the answer. This is the exact same XOR
identity that solved Single Number, applied to a different list.
Pause and answer before expanding. A wrong first guess teaches more than a fast right one.
Q1 (recall). Why is the XOR accumulator seeded with n (the array length) rather than 0?
n runs fastern - 1, so seeding n makes the full range {0..n} appear exactly once0 would throw an errorQ2 (comprehend). In the dry-run, the combined list is {0,1,2,3} XOR {3,0,1}. Why does 2 survive while 0, 1, and 3 cancel?
function missingNumber(nums):
n <- length of nums
running <- n # seed with n so 0..n is fully covered
for each index i from 0 to n - 1:
running <- running XOR i XOR nums[i] # present values cancel their index
return running
In words: a value XOR itself is nothing; a value XOR nothing is itself. The range 0..n and the array values are XOR-ed together, so every value present in both cancels, and the one value present only in the range – the missing number – is what the running XOR holds at the end.
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
int running = n;
for (int i = 0; i < n; i++) {
running ^= i ^ nums[i];
}
return running;
}
}
The accumulator is seeded with n rather than 0 because the index i
only reaches n - 1; seeding with n ensures the full target range
{0, ..., n} is represented exactly once, so every value that is in the
array pairs with its copy in the range and cancels. Each iteration XORs the
index and the value together into running, and because XOR is
commutative/associative the order of the array is irrelevant. No extra
storage is allocated – a single int – so the space is genuinely O(1),
satisfying the constant-space goal that a HashSet solution would not.
The same problem has a beautiful arithmetic solution: the sum of
{0, 1, ..., n} is n * (n + 1) / 2. Subtract the actual sum of the array
and what remains is the missing number.
class Solution {
public int missingNumber(int[] nums) {
int n = nums.length;
long expected = (long) n * (n + 1) / 2; // Gauss; cast to long to avoid overflow on the product
long actual = 0;
for (int v : nums) actual += v;
return (int) (expected - actual);
}
}
Both are O(n) time and O(1) space. The sum formula is usually easier to
explain in an interview; the XOR version is the bit-manipulation answer and
sidesteps overflow entirely (XOR never produces a value wider than its
inputs). For LeetCode’s constraints (n <= 10^4, so n*(n+1)/2 <= ~5*10^7,
well within int), either is safe; the long cast above is just defensive
habit for larger ranges.
Time: O(n) -- one pass; XOR (or addition) is O(1) per element
Space: O(1) -- a single accumulator integer
Input nums = [3, 0, 1], so n = 3 and the target range is {0, 1, 2, 3}.
Seed running = n = 3.
| Step | i | nums[i] | i ^ nums[i] (binary) | running (before) | running (after) |
|---|---|---|---|---|---|
| seed | - | - | - | - | 3 = 011 |
| 1 | 0 | 3 | 000 ^ 011 = 011 (3) |
3 = 011 |
0 = 000 |
| 2 | 1 | 0 | 001 ^ 000 = 001 (1) |
0 = 000 |
1 = 001 |
| 3 | 2 | 1 | 010 ^ 001 = 011 (3) |
1 = 001 |
2 = 010 |
Output: 2.
Why it lands on 2: think of the combined list XOR-ed together as
{0, 1, 2, 3} (the range) XOR {3, 0, 1} (the array). The 0s cancel
(range has 0, array has 0), the 1s cancel, the 3s cancel – but 2
appears only in the range, never in the array, so it survives in running.
Sanity check with the sum formula: expected = 3*4/2 = 6; actual
= 3+0+1 = 4; 6 - 4 = 2. Same answer.
Q1 (apply). Trace missingNumber([2, 0, 1]) (so n = 3, range {0,1,2,3}). What is returned?
302Q2 (analyze). Suppose you seeded the accumulator with 0 instead of n, on input nums = [0, 1, 2] (n = 3, so the true missing value is 3). What would the code return?
3 – still correct0 – wrong, because 3 is never XOR-ed into the accumulatorQ3 (transfer). The sum formula (Gauss) solves this too: expected = n*(n+1)/2, answer = expected - actual_sum. Give one advantage and one risk of the sum approach versus the XOR approach.
0 instead of n. The loop only feeds in
indices 0..n-1, so without seeding n, a missing n could never be
produced. Seeding with n covers the full range {0..n}.3 ^ 0 ^ 1
for the example, which is 2 here only by luck of this input – it does
not generalise. You must XOR the indices (and n) against the values.n * (n + 1) can exceed
Integer.MAX_VALUE for large n; cast one operand to long before the
multiply. LeetCode’s n <= 10^4 is safe, but the habit matters.[0, n] inclusive on both ends – n + 1
values total, one of which is n itself.n & (n-1) clears the lowest set bit.