Find the Missing Number in an Array of 1 to N

Title: Find the Missing Number in an Array of 1 to N

The missing-number problem is a classic warm-up for anyone preparing arrays and interview questions. You are given an array that should contain every integer from 1 to N, but exactly one value is missing. The task is to find that missing value in linear time without using any extra data structure. In this guide, you’ll learn an elegant arithmetic solution, see the full Java program, trace it on a concrete input, and walk through the edge cases that catch learners off guard.

By the end of this tutorial, you’ll understand why the formula N * (N + 1) / 2 is the key, how to guard it against integer overflow, and which interview follow-up questions build directly on this idea.

Understanding the Problem

You are given an array of N - 1 distinct integers drawn from the range 1 to N. Exactly one value in that range is absent from the array, and the order of the remaining values can be anything. Your job is to return the missing integer.

For example, if the input is:

int[] arr = {1, 2, 4, 5, 6};
int n = 6;

Then the expected output is:

int missing = 3;

A naive solution would sort the array and scan for the first gap, costing O(n log n) time. A set-based solution adds O(n) extra memory. The idea we will build runs in O(n) time and O(1) space using a simple arithmetic identity.

Approach: Sum of the First N Natural Numbers

The sum of all integers from 1 to N is known in closed form: N * (N + 1) / 2. If one value is missing from the array, then the sum of what we actually have is smaller than the expected total by exactly that missing value. Subtracting the actual sum from the expected sum gives the answer in a single pass.

Here are the steps:

1. Compute the expected sum as expectedSum = N * (N + 1) / 2 using a long to avoid overflow.
2. Initialize actualSum = 0.
3. Iterate through the array and add every element to actualSum.
4. The missing number is expectedSum - actualSum.
5. Cast the final difference back to int if your contract returns a 32-bit value.

Java Program to Find the Missing Number

Here is the complete, runnable Java program that implements the sum-based approach:

public class FindMissingNumber {

    public static int findMissing(int[] arr, int n) {
        long expectedSum = (long) n * (n + 1) / 2;
        long actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }
        return (int) (expectedSum - actualSum);
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6};
        int n = 6;
        int missing = findMissing(arr, n);
        System.out.println("Missing number: " + missing);
    }
}

Explanation of the Program

The findMissing method accepts the array arr and the upper bound n. We first compute expectedSum using the formula n * (n + 1) / 2. The cast to long matters: for large values of n the intermediate product n * (n + 1) can overflow a 32-bit int, which would silently corrupt the result.

Next we walk through the array with an enhanced for loop, accumulating every element into actualSum. Because actualSum is also a long, there is no risk of overflow during the summation either.

Finally we return the difference expectedSum - actualSum, cast back to int because the missing value fits comfortably in a 32-bit integer for any reasonable n. The main method constructs a sample array, calls findMissing, and prints the result.

Step-by-Step Trace

Let’s trace the algorithm on the input arr = [3, 1, 5, 2] with n = 5. The expected sum is 5 * 6 / 2 = 15, and the missing value should be 4. Each row shows one iteration of the for loop.

After the loop ends, actualSum holds 11. The method returns expectedSum - actualSum = 15 - 11 = 4, which is indeed the missing value. The invariant is that at the end of iteration i, actualSum equals the running total of arr[0..i-1].

Examples

Example 1: Missing Value in the Middle

The array skips 3, so the expected total of 21 minus the actual total of 18 yields 3.

int[] arr = {1, 2, 4, 5, 6};
int n = 6;
System.out.println(findMissing(arr, n));
// Output: 3

Example 2: Missing Value at the Start

When the missing value is 1, the array contains every number from 2 up to n. The subtraction still produces the correct answer without any special case.

int[] arr = {2, 3, 4, 5};
int n = 5;
System.out.println(findMissing(arr, n));
// Output: 1

Example 3: Missing Value at the End

If the missing value is n itself, the array holds 1 through n - 1. The formula handles this case identically to the others.

int[] arr = {1, 2, 3, 4};
int n = 5;
System.out.println(findMissing(arr, n));
// Output: 5

Common Mistakes to Avoid

The algorithm is short, but each line hides a trap that catches learners. Watch out for these:

• Using int for the sum – for n above roughly 65535, the product n * (n + 1) overflows a 32-bit int and the formula returns garbage. Declare both expectedSum and actualSum as long.
• Writing N * (N + 1) / 2 as (N / 2) * (N + 1) – integer division truncates when n is odd, giving the wrong expected sum. Keep the multiplication before the division so the intermediate value is even.
• Confusing n with arr.length – the array has n - 1 elements, not n. Using arr.length in place of n inside the formula yields the wrong total.
• Returning 0 when no number is missing – some learners add a check that returns 0 for a complete array. That hides the error. Prefer throwing IllegalArgumentException so callers surface the bug immediately.
• Ignoring null or wrong-sized input – passing null throws NullPointerException deep inside the loop. Validate the input at the top of the method and fail with a clear message.

Edge Cases to Test

Before you call the solution complete, run it through these inputs. They cover the boundaries interviewers probe for:

• Missing value is 1 (the first integer)
• Missing value is n (the last integer)
• Smallest valid input: n = 1 with an empty array
• Two-element input such as [2] with n = 2
• Very large n where the sum approaches Integer.MAX_VALUE
• Null array reference
• Array whose length is not n - 1

Additional Considerations

The sum-based approach runs in O(n) time because it performs a single pass over the array. It uses O(1) auxiliary memory, just two long accumulators and a loop variable, which is why it beats sorting (O(n log n)) and the HashSet approach (O(n) extra memory).

If you are nervous about overflow at the summation step, the XOR approach is an equally fast alternative. Compute xorAll = 1 ^ 2 ^ ... ^ n and xorArr as the XOR of every element in the array. The missing value is xorAll ^ xorArr. XOR is immune to overflow because each operation operates on individual bits.

Both solutions assume the array contains distinct values from 1 to n with exactly one missing entry. If duplicates or out-of-range values can appear, add a validation pass before running the arithmetic.

Interview Follow-up Questions

The missing-number problem is a launchpad for many deeper interview questions. Expect to be asked some of these:

• What if two numbers are missing instead of one? – use two equations: the sum identifies the pair’s total, and the sum of squares identifies another relationship, so you can solve a small system for both values.
• Can you solve it without the sum formula to sidestep overflow entirely? – XOR every value in the array together with every integer from 1 to n; the surviving bit pattern is the missing number.
• What if the numbers run from 0 to n instead of 1 to n? – adjust the expected sum to n * (n + 1) / 2 for the full range or shift the input by one; the logic stays the same.
• What if the input arrives as a stream and n is unknown until the stream ends? – accumulate the running sum and the running XOR; once the stream closes, derive n from the count and apply either identity.
• What if the array must be read only and you have no extra memory for intermediate values? – the current algorithm already satisfies the read-only requirement with O(1) extra memory, so cite the two accumulators as the only state you keep.

Conclusion

Finding the missing number in an array of 1 to N is a tiny problem with a surprisingly rich discussion. The sum identity gives you a one-pass, constant-memory solution that is easy to explain, easy to code, and easy to defend in an interview. Guarding the arithmetic against overflow with long is the one subtle detail you must remember.

Try adapting the program to handle two missing numbers, or switch to the XOR variant for pure integer safety. These small variations cement the pattern and prepare you for the follow-up questions interviewers love to ask.

You can learn more about array algorithms here: Arrays.