148.Missing Number

EasyBlind 75Bit Manipulation · 5/7

Problem

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.

Follow-up: can you solve it using only O(1) extra space and O(n) time?

Examples

Input:  nums = [3, 0, 1]
Output: 2
Explanation: n = 3, so the range is [0, 3]. 2 is the only number not in nums.

Input:  nums = [0, 1]
Output: 2
Explanation: n = 2, so the range is [0, 2]. 2 is missing.

Input:  nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8

Constraints

n == nums.length
1 <= n <= 10^4
0 <= nums[i] <= n
All the numbers of nums are unique.

💡 Key Insight

We know exactly which numbers should be present: 0, 1, ..., n. Combine the expected set and the actual array with an operation that cancels matching values — subtraction of sums (n(n+1)/2 - sum(nums)) or XOR (x ^ x = 0). Everything cancels except the missing number, using O(1) space.

Brute Force

TimeO(n²)SpaceO(1).

Intuition

Check each candidate 0..n one by one, scanning the array to see if it is present. The first candidate not found is the answer.

Algorithm

For candidate from 0 to n:
- Scan nums; if candidate is not found, return it.
(Unreachable) return -1.

Visualization

nums = [3, 0, 1]
candidate 0 → found ✓
candidate 1 → found ✓
candidate 2 → not found → return 2

Code

java

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

Complexity

Time: O(n²) — up to n + 1 candidates, each with an O(n) scan.
Space: O(1).

Hash Set

TimeO(n)SpaceO(n)

Intuition

Put all values into a HashSet so each "is it present?" check becomes O(1), then test 0..n.

Algorithm

Add every num to a HashSet.
For i from 0 to n, if i is not in the set, return i.

Visualization

nums = [3, 0, 1] → set = {0, 1, 3}
0 ✓  1 ✓  2 ✗ → return 2

Code

java

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

class Solution {
    public int missingNumber(int[] nums) {
        Set<Integer> present = new HashSet<>();
        for (int num : nums) {
            present.add(num);
        }
        for (int i = 0; i <= nums.length; i++) {
            if (!present.contains(i)) {
                return i;
            }
        }
        return -1; // not reached for valid input
    }
}

Complexity

Time: O(n) — two linear passes with O(1) average set operations.
Space: O(n) — the set.

Gauss Sum Formula

TimeO(n)SpaceO(1).

Intuition

The sum of 0..n is n(n + 1) / 2. The array contains all of those except one, so the difference between the expected sum and the actual sum is the missing number.

Algorithm

expected = n * (n + 1) / 2.
actual = sum(nums).
Return expected - actual.

Visualization

nums = [3, 0, 1], n = 3
expected = 3 * 4 / 2 = 6
actual   = 3 + 0 + 1 = 4
missing  = 6 - 4 = 2

Code

java

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int expected = n * (n + 1) / 2; // sum of 0..n (fits in int for n ≤ 10^4)
        int actual = 0;
        for (int num : nums) {
            actual += num;
        }
        return expected - actual;
    }
}

Complexity

Time: O(n) — one pass to sum.
Space: O(1).

XOROptimal

TimeO(n)SpaceO(1).

Intuition

XOR every index 0..n together with every value in nums. Each present number appears twice in that combined list (once as an index/expected value, once as an array value) and cancels to 0. The missing number appears only once, so it is what remains. Unlike the sum, XOR can never overflow, no matter how large n gets.

Algorithm

result = n (the index n has no array slot, so seed it here).
For i from 0 to n - 1: result ^= i ^ nums[i].
Return result.

Dry Run

flowchart LR
    A["result = n = 3"] -->|"^ i=0 ^ nums[0]=3"| B["3^0^3 = 0"]
    B -->|"^ i=1 ^ nums[1]=0"| C["0^1^0 = 1"]
    C -->|"^ i=2 ^ nums[2]=1"| D["1^2^1 = 2"]
    D --> E["return 2"]

all values XORed: 3 ^ (0 ^ 3) ^ (1 ^ 0) ^ (2 ^ 1)
regrouped:        (0 ^ 0) ^ (1 ^ 1) ^ (3 ^ 3) ^ 2 = 2

Code

java

class Solution {
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int result = n; // index n has no slot in the array, include it up front
        for (int i = 0; i < n; i++) {
            result ^= i ^ nums[i]; // matching index/value pairs cancel out
        }
        return result;
    }
}

Complexity

Time: O(n) — one pass.
Space: O(1).

Complexity Comparison

Approach	Time	Space
Brute Force	O(n²)	O(1)
Hash Set	O(n)	O(n)
Gauss Sum	O(n)	O(1)
XOR	O(n)	O(1)

Common Pitfalls

Forgetting that the range is [0, n] (size n + 1), not [1, n] — the missing number can be 0 or n.
In the XOR solution, forgetting to include n itself — then an input like [0, 1] would wrongly return 0 instead of 2.
Overflow in the sum formula for large n (n(n+1)/2 exceeds int around n ≈ 65,000) — fine here, but use long or XOR in general.
Sorting first and scanning for a gap works but costs O(n log n) and mutates the input.