☕ DSA Java Articles

Topics › Arrays › Easy

Find missing number

Easy TUF ID 44 A2ZBlind 75

LeetCode ↗ Java source ↗ Edit this article ↗

Problem

You are given an array nums of n distinct integers, each in the range 0 .. n. Exactly one value from that range is absent; return it.

The A2Z sheet phrases the same problem with values 1 .. N and an array of length N - 1; the Java file includes missingFromOneToN for that wording, and every approach below carries over with the range shifted by one.

Constraints: 0 ≤ n ≤ 10^5, so the sum 0 + 1 + ... + n can reach about 5 × 10^9 and no longer fits in an int.

Example 1

nums = [3, 0, 1]
answer = 2              // n = 3, range 0..3, the only value absent is 2

Example 2

nums = [0, 1]
answer = 2              // the missing value can be n itself

Example 3

nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
answer = 8

The problem looks like a search, and the first two approaches treat it as one. The last two notice that it is really an accounting problem: we know exactly what the complete set should be, so comparing the complete set with what we have reveals the missing item without searching for anything.

Approach 1: Brute force, search for every candidate

Intuition. For each value candidate in 0 .. n, scan the array to see whether it is present. The first candidate that is not found is the answer. This is n + 1 linear searches.

Algorithm.

  1. For candidate from 0 to n:
  2. Scan nums; if some element equals candidate, mark it present and stop scanning.
  3. If candidate was not found, return it.
static int bruteForce(int[] nums) {
    int n = nums.length;
    for (int candidate = 0; candidate <= n; candidate++) {
        boolean present = false;
        for (int x : nums) {
            if (x == candidate) { present = true; break; }
        }
        if (!present) return candidate;
    }
    return -1;                                   // unreachable for valid input
}

Complexity. Time O(n^2): up to n + 1 candidates, each costing up to n comparisons. Space O(1).

For n = 10^5 that is 10^10 operations in the worst case (the missing value is n). The tests only run this method on small inputs for that reason.

Approach 2: Better, mark what you have seen

Intuition. Instead of searching the array once per candidate, read the array once and record which values occur in a boolean table indexed by value. Then the missing value is the first index that was never marked. This trades O(n) extra memory for a factor of n in time; it is the “hashing” solution, and because the values are small non-negative integers, a plain array is the perfect hash.

Algorithm.

  1. Allocate seen of size n + 1, all false.
  2. For each x in nums, set seen[x] = true.
  3. Return the first v in 0 .. n with seen[v] == false.
static int better(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
}

Complexity. Time O(n): two linear passes. Space O(n) for the table.

This is also the approach that degrades most gracefully when the problem’s promises are broken: if the input has duplicates or several missing values, the table still tells you exactly which values are absent.

Approach 3: Optimal, the sum formula

Intuition. The sum of 0 .. n is n(n + 1) / 2. The array contains every one of those values except one, so expectedSum - actualSum is precisely the missing value. One pass, one subtraction, no extra memory.

The arithmetic must be done in long. With n = 10^5 the expected sum is 5,000,050,000, which exceeds Integer.MAX_VALUE (2,147,483,647). Writing n * (n + 1) / 2 in int overflows before the division and produces garbage; the cast (long) n must come first so that the multiplication happens in 64 bits.

Algorithm.

  1. expected = n(n + 1) / 2 computed in long.
  2. actual = sum of nums accumulated in long.
  3. Return expected - actual.
static int optimalSum(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);
}

Dry run on nums = [3, 0, 1]: n = 3, expected = 3 × 4 / 2 = 6, actual = 3 + 0 + 1 = 4, answer 6 - 4 = 2.

Complexity. Time O(n), space O(1).

Approach 4: Optimal, XOR cancellation

Intuition. XOR has two properties that make it a counting device for “appears an odd number of times”: x ^ x = 0 and x ^ 0 = x, and it is commutative and associative, so order does not matter. XOR together all the values 0 .. n and all the elements of the array. Every value that is present appears twice (once from the range, once from the array) and cancels to zero. The missing value appears exactly once, from the range only, and survives.

This avoids the overflow question entirely: XOR never produces a result wider than its inputs.

Algorithm.

  1. xor = 0.
  2. For each index i, fold in both i and nums[i]: xor ^= i ^ nums[i]. After the loop, indices 0 .. n - 1 and all array values are included.
  3. The index n has no array slot, so fold it in separately: return xor ^ n.
static int optimalXor(int[] nums) {
    int xor = 0;
    for (int i = 0; i < nums.length; i++) xor ^= i ^ nums[i];
    return xor ^ nums.length;                    // the index n has no array slot, fold it in separately
}

Dry run on nums = [3, 0, 1]: the folded values are 0, 3, 1, 0, 2, 1 from the loop and then 3. Pairing them up: 0 ^ 0 = 0, 1 ^ 1 = 0, 3 ^ 3 = 0, leaving 2. Answer 2.

Complexity. Time O(n), space O(1).

Sum and XOR are equally fast; XOR is the one to show when you want to signal that you know the overflow pitfall exists, and it generalises to Find the number that appears once, and other numbers twice., where no sum formula is available.

The 1 .. N wording

static int missingFromOneToN(int[] nums, int N) {
    int xor = 0;
    for (int v = 1; v <= N; v++) xor ^= v;
    for (int x : nums) xor ^= x;
    return xor;
}

Same cancellation argument with the range 1 .. N. Here N must be passed in because it is no longer recoverable from the array length alone in a way the reader will find obvious (N = nums.length + 1).

Edge cases and pitfalls