A gate agent scans boarding-pass seat numbers. The aircraft has seats 0 through n; the scan file holds n distinct ids from that range — one seat never boarded. The first version sorted the scans and walked looking for the first index that was not the seat id. A 50-seat regional returned before the jetway moved. A widebody turnaround was still sorting when the door-close clock hit.

Missing Number asks for the one absent value in 0..n. An array already gives nums[i] for free. Sorting uses that and still pays O(n log n). A HashSet of the scans answers in a probe of 0..n and still allocates a bucket per boarded seat.

This is an interview writeup, not a bit-twiddling lecture. XOR cancels a value against itself. Here we only care that pairing every index with every stored seat leaves the empty one standing.

The problem

Given an int[] nums of length n whose values are n distinct integers from the closed range 0 through n, return the single integer in that range that does not appear.

nums = [4, 0, 2, 1]   n = 4, range 0..4   →  3
nums = [1]            n = 1, range 0..1   →  0
nums = [0]            n = 1, range 0..1   →  1
nums = [2, 0, 1]      n = 3, range 0..3   →  3

Note: The missing value can be 0, n, or anything in between. After a sort, a walk that only checks nums[i] != i still has to return n when the file is [0, 1, …, n-1] with nothing out of place.

Sort or a set is the honest brute force

Sort, then the first index whose value is not the index is the empty seat. If the walk finishes, the empty seat is n. Correct. O(n log n), and it permutes an array you were not asked to reorder.

int missingSorted(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != i) {
            return i;
        }
    }
    return nums.length;
}

A HashSet of the n values, then a probe of 0..n for the first miss, is the same answer with expected linear time and O(n) extra space. At a widebody you paid a sort or a set for a question the range itself already answers: which integer in 0..n has no partner in the file?

XOR the range with the file

a ^ a is 0. a ^ 0 is a. Order does not matter. XOR every index 0..n-1 with every nums[i], and fold in n once. Each boarded seat appears twice — once as a stored value, once as its matching index — and cancels. The missing seat appears only as an index (or only as the folded-in n) and survives.

Start the running XOR at n so the top of the range is in the mix even though it is not a legal index of the file.

nums = [4, 0, 2, 1]   n = 4   missing starts at 4

i=0  4 ^ 0 ^ 4 = 0
i=1  0 ^ 1 ^ 0 = 1
i=2  1 ^ 2 ^ 2 = 1
i=3  1 ^ 3 ^ 1 = 3

The Java is that fold:

int missingNumber(int[] nums) {
    int n = nums.length;
    int missing = n;
    for (int i = 0; i < n; i++) {
        missing ^= i ^ nums[i];
    }
    return missing;
}

Time is O(n) — one pass, constant work per index. Space is O(1) besides the running XOR.

Gauss is the same pairing with arithmetic: the closed sum 0..n is n(n+1)/2; subtract the array sum. Same linear pass, same constant extra. Do the sum in long. n * (n + 1) as int overflows once n is a few tens of thousands — the multiply happens before the divide. XOR never has that bill.

int missingBySum(int[] nums) {
    int n = nums.length;
    long expected = (long) n * (n + 1) / 2;
    long actual = 0;
    for (int x : nums) {
        actual += x;
    }
    return (int) (expected - actual);
}

Note: Casting n to long before the multiply is the whole trick. Casting the result of an int multiply is too late: the overflow already wrapped.

What interviewers usually poke next

  • Overflow. Name the long Gauss path out loud. XOR is the answer that does not care.
  • Missing is n. The running XOR must include n. Starting at 0 and folding only i ^ nums[i] drops the top of the range.
  • Range 1..n with one missing. Same idea; fold 1..n (or n(n+1)/2) against the file. Do not assume 0 is in play.
  • Two missing, or a duplicate instead. XOR of the whole range no longer isolates one value. That is a different prompt — counting, a set, or the duplicate-as-cycle walk — not a second XOR identity.
  • Sort anyway. Legal if they allow mutation. Say the O(n log n) bill and why XOR is still the default when they asked for linear time and constant extra memory.

You are done with this problem when you can say, out loud, why sort and a set are correct, why Gauss needs a wider sum, and why XOR of the indexes with the values leaves the empty seat.