Missing Number (LC 268)

Pattern: Bit Manipulation (XOR) / Math
Difficulty: Easy
Key Concept: XOR every index with every value; pairs (i, nums[i]) for present numbers cancel—what remains is the missing index.

Problem Statement

Given an array nums containing n distinct numbers taken from the range [0, n], return the only number in the range that is missing from the array.

Input

• nums: int[] of length n, containing distinct integers from [0, n] with exactly one missing

Output

• int — the missing integer

Example

• nums = [3, 0, 1] → 2
• nums = [0, 1] → 2

Constraints (typical)

• n == nums.length
• 1 <= n <= 10^4

---

1. Algorithm & Pseudocode

Brute force

Put all numbers in a HashSet, then scan 0..n for which is absent.

set = all nums[i]
for k from 0 to n:
    if k not in set:
        return k

Or sort and find the gap — O(n log n).

Optimal (XOR)

XOR is associative/commutative, and x ^ x = 0, x ^ 0 = x.

xor = 0
for i from 0 to n-1:
    xor ^= i ^ nums[i]
xor ^= n
return xor

Every value that appears cancels with its index except the missing number’s index never gets paired with itself as a value in the right way—equivalently: XOR all indices 0..n and all nums[i]; duplicates cancel conceptually (see analysis).

Cleaner equivalent: xor = 0; for i: xor ^= i ^ nums[i]; xor ^= n;

Optimal (Gauss sum)

missing = n*(n+1)/2 - sum(nums).

---

2. Step-by-Step Analysis (Beginner-Friendly)

1. Why XOR works Think of XOR as “toggle.” If you XOR the same number twice, it undoes. Include every number from 0 to n exactly once in an “expected” multiset, and XOR in everything that actually appears in nums. The value that was not in nums appears one extra time in the “expected” side—after cancellation, only the missing value remains.

2. Concrete pairing view Let missing = m. XOR all of {0,1,...,n} with all elements of nums. Each nums[i] that is not m appears alongside some other structure; the standard linear code XORs i with nums[i] and finally n to fold in the full range cleanly.

3. Why include n The array has indices 0..n-1 but values live in 0..n. The loop xor ^= i ^ nums[i] processes pairs (index, value); XOR-ing n afterward accounts for the full set {0..n} on the “index side” style formulations—the given code is the standard compact form:

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

Here nums.length is n, and we XOR indices 0..n-1 with all values, then XOR n to complete the 0..n range.

4. Sum formula intuition Expected total minus actual total equals the missing number—watch integer overflow on huge n (use long if needed).

---

3. The Dry Run

Sample: nums = [3, 0, 1] (n = 3). XOR approach.

Step	i	nums[i]	i ^ nums[i]	running x
init	—	—	—	0
1	0	3	0^3 = 3	3
2	1	0	1^0 = 1	3^1 = 2
3	2	1	2^1 = 3	2^3 = 1
end	—	—	XOR n = 3	1^3 = 2

Result: 2 (missing).

ASCII: cancelation idea

Values present: 3, 0, 1
Full set 0..3:  0, 1, 2, 3

XOR everything: each of 0,1,3 appears twice -> cancel
Lone survivor: 2

---

4. Java Solution

Brute Force

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int x : nums) {
            set.add(x);
        }
        int n = nums.length;
        for (int k = 0; k <= n; k++) {
            if (!set.contains(k)) {
                return k;
            }
        }
        return -1; // unreachable given problem guarantees
    }
}

Time: O(n) average for HashSet operations.
Space: O(n).

Optimal (XOR)

class Solution {
    public int missingNumber(int[] nums) {
        int x = 0;
        for (int i = 0; i < nums.length; i++) {
            x ^= i ^ nums[i];
        }
        x ^= nums.length;
        return x;
    }
}

Time: O(n).
Space: O(1).

Optimal (Sum with long)

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        long total = (long) n * (n + 1) / 2;
        long sum = 0;
        for (int v : nums) {
            sum += v;
        }
        return (int) (total - sum);
    }
}

Time: O(n).
Space: O(1).

---

5. The “Java vs. Others” Edge

• Overflow n*(n+1)/2 as int can overflow for large n; use long for the accumulator (LeetCode constraints often allow int, but seniors mention overflow).
• Set vs XOR Java HashSet costs extra memory; XOR is O(1) space and cache-friendly.
• Python XOR is the same; sum approach is popular because big integers avoid overflow—Java needs explicit long.

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute (HashSet)	O(n)	O(n)	Clear, interview-safe.
Sort + scan	O(n log n)	O(1) or O(n)	Not ideal unless asked.
XOR	O(n)	O(1)	Elegant, no overflow issues from sums.
Gauss sum	O(n)	O(1)	Use long for intermediate totals.