easy Missing Number

Missing Number

You are given an array nums containing n distinct numbers drawn from the range [0, n] — that is, n + 1 possible values but only n of them present. Exactly one value in [0, n] is missing; return it. For nums = [3, 0, 1] (n = 3, range 0..3), the missing number is 2.

There are several correct answers here, and choosing between them is the actual interview. The naive one sorts or hashes; the arithmetic one is a one-liner with a landmine; the XOR one is landmine-free. Knowing why XOR is the safe pick — not just that it works — is the differentiator.

Baselines and their costs

• Sort, then scan for the first gap. O(n log n) time. Simple, but throws away the fact that the values are a near-complete 0..n.
• Hash set. Insert all of nums, then probe 0..n for the absentee. O(n) time but O(n) extra space.
• Sum formula. The complete set 0..n sums to n(n+1)/2 (Gauss). Subtract the actual sum of nums and the difference is the missing value. O(n) time, O(1) space — but the intermediate sum can overflow a 32-bit int for large n.

The bit insight — XOR the indices against the values

XOR has two properties we will lean on, both provable from its truth table: it is self-cancelling (a ^ a = 0, since each bit XORed with itself is 0) and it has an identity (a ^ 0 = a). It is also commutative and associative, so a long XOR chain can be reordered freely — equal terms will find each other and vanish in pairs.

Now line up two sequences: the indices 0, 1, 2, …, n (that is the full range [0, n]) and the values in nums. XOR all of them together into one accumulator. Every number that is actually present appears twice in that combined pile — once as a member of the index range and once as an element of nums — so it cancels to 0. The one missing number appears only once (it is in the range but not in the array), so it is the lone survivor. XOR literally cancels every matched pair and leaves the unmatched value.

Concretely, we fold the range and the array into a single accumulator: start at 0, XOR in each index i and each nums[i], then XOR in the final index n (there is no nums[n], since the array has only n elements at indices 0..n-1).

Traced example — nums = [3, 0, 1], n = 3

We accumulate acc ^= i ^ nums[i] for i = 0, 1, 2, then acc ^= 3. Bits shown are 2-bit patterns (values 0..3):

The survivor is 2. Sanity check by grouping the whole XOR pile: indices {0,1,2,3} and values {3,0,1} together are 0,1,2,3,3,0,1. Pair them off: the two 0s cancel, the two 1s cancel, the two 3s cancel, and 2 stands alone. Answer 2, matching the trace.

Java: XOR index against value

public class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int acc = n;                    // seed with the top index n (no nums[n] exists)
        for (int i = 0; i < n; i++) {
            acc ^= i ^ nums[i];         // cancel index i against value nums[i]
        }
        return acc;
    }

    public static void main(String[] args) {
        System.out.println(new Solution().missingNumber(new int[]{3, 0, 1}));       // 2
        System.out.println(new Solution().missingNumber(new int[]{0, 1}));          // 2
        System.out.println(new Solution().missingNumber(new int[]{9,6,4,2,3,5,7,0,1})); // 8
    }
}

Go: XOR index against value

package main

import "fmt"

func missingNumber(nums []int) int {
	n := len(nums)
	acc := n // seed with the top index n (no nums[n] exists)
	for i := 0; i < n; i++ {
		acc ^= i ^ nums[i] // cancel index i against value nums[i]
	}
	return acc
}

func main() {
	fmt.Println(missingNumber([]int{3, 0, 1}))              // 2
	fmt.Println(missingNumber([]int{0, 1}))                 // 2
	fmt.Println(missingNumber([]int{9, 6, 4, 2, 3, 5, 7, 0, 1})) // 8
}

Complexity

• Time: one pass, two XORs per element → O(n).
• Space: a single accumulator → O(1).

Same asymptotics as the sum formula and better than sort's O(n log n); same space as the sum formula and better than the hash set's O(n).

Why XOR is preferred when overflow matters

The sum formula and XOR are both O(n)/O(1), so the deciding factor is numerical safety. The sum approach computes n(n+1)/2, a quantity that grows with the input and can exceed Integer.MAX_VALUE (2³¹−1). It overflows around n ≈ 65536 (where n(n+1)/2 passes 2³¹), silently wrapping to a wrong answer unless you widen to long. XOR never grows: a bit of the accumulator is set only if some input had that bit set, so the result's highest set bit can never rise above the highest set bit of the largest input — the accumulator stays inside the inputs' bit-width and cannot overflow. (It may still exceed an individual input in value — 1 ^ 2 = 3 — but never the word width.) That is the crisp reason to prefer it: not that it is cleverer, but that it removes an entire failure mode.

Judgment layer — sum vs. XOR vs. sort vs. hash

• In the interview: lead with the hash set to establish a correct baseline, then improve to O(1) space. Between the two O(1)-space options, present XOR and explicitly note it sidesteps the sum's overflow — that reasoning is the signal, not the trick itself.
• When the sum formula is actually the better call: if the values are not a clean permutation of an index range (e.g. arbitrary reals, or the “missing” is defined by magnitude), XOR's pairing argument collapses and arithmetic is the only thing that generalizes. XOR is specifically a tool for “every element pairs with exactly one other except the answer.”
• Don't over-index on cleverness: if a teammate will read this code, the hash set or a long-typed sum may be the more maintainable choice. Reserve XOR for when O(1) space is a hard requirement or the interviewer asks for it.

Edge cases & traps

• Seed with n, not 0. The array holds only indices 0..n-1, so the top index n is never produced by the loop — you must XOR it in separately (here, as the accumulator's initial value). Forgetting it is the #1 bug.
• Missing number is 0: e.g. nums = [1], n = 1. Range {0,1}, values {1} → the two 1s cancel, leaving 0. The algorithm handles it with no special case.
• Missing number is n itself: e.g. nums = [0, 1, 2], n = 3. All of 0,1,2 cancel, leaving the seeded n = 3. Also handled.
• Sum-formula overflow: in Java, n * (n + 1) / 2 in int arithmetic overflows for large n; compute it in long. XOR has no such caveat.

Takeaways

• XOR every index 0..n against every value; matched pairs cancel (a ^ a = 0) and the missing number is the sole survivor (a ^ 0 = a).
• XOR and the sum formula are both O(n)/O(1); XOR wins because its accumulator can never overflow, while n(n+1)/2 can.
• Seed the accumulator with the top index n — the loop only covers 0..n-1.
• XOR is the right tool precisely when the data is a permutation-with-one-hole; when it is not, fall back to arithmetic or hashing.