Find Two Missing Numbers in an Array

Title: Find Two Missing Numbers in an Array

In this guide, you will learn how to find two missing numbers in an array that should have contained every integer from 1 to n + 2 exactly once, but is missing two of them. This is a popular interview variant of the classic single missing number problem, and it tests whether you can extend a simple sum trick into a two-step technique.

We will build the solution step by step, starting with the math behind the sum trick, moving to a full Java program, then walking through a dry run, examples, common mistakes, edge cases, and a set of interview follow-up questions you should be ready for.

Understanding the Problem

You are given an array numbers of length n that should have contained every integer from 1 to n + 2 exactly once, but two of those integers are missing from the array. The array may or may not be sorted.

Your task is to find both missing numbers using only the numbers that are present, ideally in O(n) time and O(1) extra space. For example, if numbers = [1, 2, 4, 5, 6, 8, 9], the full range is 1 to 9, and the two missing numbers are 3 and 7.

Approach / Algorithm Steps

The core idea extends the single-missing-number sum trick into two passes: one pass finds the combined sum of both missing numbers, and a second pass splits the range in half to isolate each one.

1. Compute totalRange = n + 2, the size of the full range 1..totalRange that the array would contain if no numbers were missing.
2. Compute expectedTotalSum, the sum of every number from 1 to totalRange, using the formula totalRange * (totalRange + 1) / 2.
3. Traverse the array once to compute actualSum, the sum of the numbers that are actually present.
4. Compute missingSum = expectedTotalSum - actualSum; this equals the sum of the two missing numbers.
5. Compute mid = missingSum / 2 to split the full range into a lower half 1..mid and an upper half mid + 1..totalRange; exactly one missing number falls in the lower half.
6. Compute expectedLowerSum, the sum of 1..mid, using the same sum formula.
7. Traverse the array a second time, adding only the numbers that are <= mid, to get actualLowerSum.
8. Compute first = expectedLowerSum - actualLowerSum and second = missingSum - first; these are the two missing numbers.

Java Program

Here is a complete, compilable program that implements the approach above.

import java.util.Arrays;

public class FindTwoMissingNumbers {

    public static int[] findTwoMissingNumbers(int[] numbers, int n) {
        int totalRange = n + 2;
        long expectedTotalSum = (long) totalRange * (totalRange + 1) / 2;

        long actualSum = 0;
        for (int number : numbers) {
            actualSum += number;
        }

        long missingSum = expectedTotalSum - actualSum;
        long mid = missingSum / 2;

        long expectedLowerSum = mid * (mid + 1) / 2;
        long actualLowerSum = 0;
        for (int number : numbers) {
            if (number <= mid) {
                actualLowerSum += number;
            }
        }

        int first = (int) (expectedLowerSum - actualLowerSum);
        int second = (int) (missingSum - first);

        return new int[] { first, second };
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 4, 5, 6, 8, 9};
        int n = numbers.length;

        int[] missing = findTwoMissingNumbers(numbers, n);

        System.out.println("Missing numbers: " + Arrays.toString(missing));
    }
}

Explanation of the Program

The method findTwoMissingNumbers first computes totalRange, which is n + 2 since two numbers are missing from an array of length n. It then uses the sum-of-first-k-integers formula to compute expectedTotalSum, the total the array would sum to if nothing were missing.

A single pass over numbers accumulates actualSum, the sum of the values that are actually present. Subtracting actualSum from expectedTotalSum gives missingSum, the combined sum of the two missing numbers.

mid splits the full range in half. Because missingSum is the sum of exactly two numbers, dividing it by two always lands strictly inside the range, so exactly one missing number falls in 1..mid and the other falls in mid + 1..totalRange.

A second pass over numbers sums only the values <= mid into actualLowerSum. Comparing it against expectedLowerSum, the sum of 1..mid, isolates first, the missing number in the lower half. The second missing number falls out of missingSum - first.

Step-by-Step Trace

Consider numbers = [1, 3, 4, 6, 7, 8] with n = 6, so the full range is 1 to 8 and the target output is the pair 2 and 5. The table below traces the first loop, which accumulates runningSum (the same variable as actualSum in the program).

At the end of iteration i, runningSum holds the sum of numbers[0..i].

After the loop finishes, runningSum is 29, so missingSum = 36 - 29 = 7 and mid = 7 / 2 = 3. A second pass sums the values <= 3, which is just 1 + 3 = 4, giving expectedLowerSum - actualLowerSum = 6 - 4 = 2 as the first missing number, and missingSum - first = 7 - 2 = 5 as the second.

Examples

Example 1: Missing Numbers at the Boundaries of the Range

When the two missing numbers are the smallest and largest values in the range, the lower-half pass still isolates them correctly.

int[] numbers = {2, 3, 4, 5, 6, 7, 8, 9, 10};
int n = numbers.length;

int[] missing = findTwoMissingNumbers(numbers, n);
// missing = [1, 11]

Example 2: Missing Numbers Scattered in the Middle

The two missing numbers do not need to be adjacent for the algorithm to work, since the split only cares about which side of mid each missing number falls on.

int[] numbers = {1, 2, 3, 4, 6, 7, 9, 10};
int n = numbers.length;

int[] missing = findTwoMissingNumbers(numbers, n);
// missing = [5, 8]

Common Mistakes to Avoid

These are the mistakes learners most often make when adapting the single-missing-number trick to the two-missing-numbers version.

• Using n + 1 as the total range – treats this like the single-missing-number problem and silently shifts both results by one. Use n + 2, since two numbers are absent from an array of length n.
• Summing into an int accumulator – works on small test arrays but overflows silently once n and the range grow large. Accumulate into long and only cast back to int for the final missing values.
• Assuming the input must be sorted first – sorting before running the sum passes adds unnecessary O(n log n) overhead. The sum-splitting approach works on the array in its original order.
• Using < mid instead of <= mid in the second pass – excludes mid from the lower-half sum whenever mid is actually present in the array, producing a first value that is off by mid‘s contribution. Match the same boundary used when computing expectedLowerSum.

Edge Cases to Test

Walk through these input shapes before calling the solution complete.

• Missing numbers at both boundaries (1 and n + 2)
• Array already sorted
• Array in random order
• Missing numbers adjacent to each other
• Minimum-size array (n = 1, a range of three numbers with two missing)
• Large n with potential sum overflow
• Duplicate values in the array
• Null array reference

Additional Considerations

The algorithm runs in O(n) time, since it makes exactly two linear passes over numbers, and uses only O(1) extra space beyond the input array.

Using long for expectedTotalSum, actualSum, and the other running totals matters once n is large, since the formula-based sums grow quadratically with totalRange and can exceed Integer.MAX_VALUE well before the array itself becomes unwieldy.

A simpler alternative is to mark presence in a boolean array sized totalRange + 1 and scan for the two unmarked indices, but that costs O(n) extra space instead of O(1). Sorting the array first and scanning for the two gaps works too, but that costs O(n log n) time for no benefit over the sum-splitting approach.

Interview Follow-up Questions

Be ready for an interviewer to push the problem in one of these directions.

• What if the array contains duplicate values? – switch to a presence check such as a boolean array or a HashSet, since duplicates break the one-to-one correspondence the sum trick relies on.
• What if you needed to find the k missing numbers for k > 2? – generalize the bisection: after splitting at the midpoint, recursively repeat the sum-split technique on whichever half still contains more than one missing value.
• What if the numbers arrived as a one-pass stream that could not be buffered? – you can still compute the combined missing sum in one pass, but isolating the individual values needs a second signal, such as an XOR-based trick, rather than a second traversal of the stream.
• What if n is large enough that even long running totals risk overflow? – track the sum using an average-and-count pair or arbitrary-precision arithmetic instead of accumulating one very large running total.

Conclusion

Finding two missing numbers in an array builds directly on the single-missing-number sum trick: compute the combined sum of the missing values, then split the range in half and repeat the same trick on one side to isolate each number individually. The approach stays O(n) time and O(1) extra space as long as you watch for overflow and handle duplicates separately.

Try adapting the same bisection idea to find three or more missing numbers, or to work against a read-only stream instead of an array. You can learn more about array-based problems like this one in our Arrays category.