LeetCode 268 · Easy · Bit Manipulation

Missing Number

nums holds n distinct numbers taken from 0 to n, so exactly one number in that range is absent. Return it using O(1) extra space.

O(n)time
O(1)space
XORindices against values

1–12 distinct integers, each from 0 to n, where n is how many you enter

nums

res ^ i ^ nums[i] column by column: a 1 when the column has an odd number of 1s

0 … n, XORed in an odd number of times each number enters once as an index or as n, and once as a value · res = XOR of the lit ones

public int missingNumber(int[] nums) { int res = nums.length; // n: the one index the loop skips for (int i = 0; i < nums.length; i++) { res ^= i ^ nums[i]; } return res;}
i
—
nums[i]
—
res
—

Why it works

  1. Brute force: sort and look for the first index where nums[i] != i (O(n log n)), or put the values in a HashSet and test 0 … n (O(n) space).
  2. Pair every number with itself. XOR all indices 0 … n − 1, plus n, and all values. Each number from 0 to n shows up once on the index side; every number except the missing one also shows up once on the value side. Pairs cancel (x ^ x = 0), so only the missing number survives.
  3. One pass, one integer: O(n) time, O(1) space. XOR cannot overflow, unlike a running sum in an int.
  4. Pitfall: n itself. i < nums.length stops at n − 1, so n would never get its index-side partner. Starting res at nums.length adds it. Without that, an input missing n returns a wrong answer.
  5. Alternative: Gauss's sum, n·(n + 1)/2 − (sum of nums), or the same loop with res += i − nums[i]. Single Number (136) is the same cancellation trick.