Missing Number

EasyBit Manipulation · XOR · Math🧩 Bit Manipulation LeetCode #268 ↗Updated Oct 30, 2026

Problem

An array nums of length n holds distinct numbers taken from 0, 1, …, n. Exactly one value from that range of n + 1 numbers is absent. Return it.

Input[3,0,1]Output2

Input[0,1]Output2

Input[9,6,4,2,3,5,7,0,1]Output8

1 ≤ n ≤ 10⁴ · 0 ≤ nums[i] ≤ n · all values distinct · Follow-up: O(1) extra space and O(n) time.

Try it yourself

Java

class Solution {
    public int missingNumber(int[] nums) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

XOR every index 0..n with every value in the array. Each present number appears twice and cancels (x ^ x = 0); the only survivor is the missing one.

PatternBit Manipulation

Instinct Pairs that cancel, counting 1s, powers of two, subsets as numbers, or 'no + or - allowed' - drop to binary and use XOR, AND, OR and shifts.

Memory hack XOR is a forgetful twin detector - see something twice and it vanishes; n & (n-1) snips off the last lit bulb.

Open the Bit Manipulation guide →

Approaches

Brute ForceSearch for Each Candidate

Time O(n²)Space O(1)

Try every candidate 0..n and linearly scan the array for it. The first candidate that is never found is the answer.

Java

public int missingNumber(int[] nums) {
    int n = nums.length;
    for (int candidate = 0; candidate <= n; candidate++) {
        boolean found = false;
        for (int x : nums) {
            if (x == candidate) {
                found = true;
                break;
            }
        }
        if (!found) return candidate;
    }
    return -1; // unreachable for valid input
}

Trivially correct, but quadratic.

BetterPresence Array

Time O(n)Space O(n)

Mark each value in a boolean[n + 1]. Then scan the marks; the one slot still false is the missing number. Values are bounded by n, so the array is a perfect hash table.

Java

public int missingNumber(int[] nums) {
    int n = nums.length;
    boolean[] seen = new boolean[n + 1];
    for (int x : nums) seen[x] = true;
    for (int v = 0; v <= n; v++) {
        if (!seen[v]) return v;
    }
    return -1; // unreachable for valid input
}

Linear time, but O(n) extra memory misses the follow-up.

OptimalXOR Cancellation

Time O(n)Space O(1)

Start with xor = n (the one index the loop won’t reach), then fold in i ^ nums[i] for every i. XOR is order-independent and self-cancelling, so all paired numbers vanish and only the missing value is left.

Java

public int missingNumber(int[] nums) {
    int xor = nums.length; // index n has no array slot
    for (int i = 0; i < nums.length; i++) {
        xor ^= i ^ nums[i];
    }
    return xor;
}

Dry run[3,0,1]

i index changed

init
3

0

1

xor = n = 3
i=0
3
i
0

1

3^0^3 = 0
i=1
3

0
i
1

0^1^0 = 1
i=2
3

0

1
i
1^2^1 = 2 ✔

One pass, constant memory, no overflow concerns.

Pro tip

Gauss alternative: n(n+1)/2 − sum(nums) — also O(1) space, but mention overflow for large n.

At a glance

Level	Approach	Time	Space
Brute Force	Search for Each Candidate	`O(n²)`	`O(1)`
Better	Presence Array	`O(n)`	`O(n)`
Optimal	XOR Cancellation	`O(n)`	`O(1)`

Common pitfalls

Forgetting n itself can be missing (e.g. [0,1] → 2).
Starting the XOR at 0 instead of n — index n never gets folded in.
Sum formula overflow in languages or variants with large n.

Interview tips

Name the XOR properties: x^x = 0, x^0 = x, order doesn’t matter.
Offer the Gauss-sum version as an equally valid O(1)-space alternative.
Sorting then scanning is another O(n log n) middle ground worth mentioning.

Pattern

XOR pairing → find the one value without a partner when everything else appears an even number of times.

My notes saved in this browser