easyArray ProblemsJava

Find the Missing Number in an Array of 1 to N

Find the single missing number from an array holding 1..N with one value absent.

Quick Answer

The numbers 1 to N add up to N*(N+1)/2. Sum the array you actually have, then subtract it from that expected total. The difference is the one missing number. This runs in O(n) time with O(1) extra space.

Problem Statement

An array contains the numbers from 1 to N with exactly one number missing, so its length is N - 1. Find the missing number.

The array is not necessarily sorted. Return the missing value. Use the arithmetic series sum so you avoid sorting or an extra lookup structure.

Input: An array arr of length N - 1 holding distinct values from 1..N with one missing.

Output: The single missing integer.

Examples

Example 1
Input:  [1, 2, 4, 5]
Output: 3

Here N = 5, so the expected sum is 15; the actual sum is 12, and 15 - 12 = 3.

Example 2
Input:  [2, 3, 1, 5]
Output: 4

N = 5, expected sum 15, actual sum 11, so the missing number is 15 - 11 = 4.

Constraints

  • 1 <= N <= 10^6, so arr.length = N - 1
  • All present values are distinct and in the range 1..N

Think Before You Code

Reveal the questions to ask yourself first
  • What is N in terms of the array's length?
  • Is there a closed-form total for the numbers 1 through N?
  • How does subtracting the actual sum reveal the gap?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
The full set 1..N has a known total; the array is missing exactly one of them.
Hint 2
The sum of 1..N is `N * (N + 1) / 2`. Here N is `arr.length + 1`.
Hint 3
Subtract the sum of the array from that expected total; the difference is the missing number. Use `long` to avoid overflow.

Approach

Reveal the step-by-step approach

Use the arithmetic series total, then subtract what is present.

  1. Compute n = arr.length + 1 (the intended largest value).
  2. Compute the expected sum expected = n * (n + 1) / 2.
  3. Compute the actual sum of the array's elements.
  4. Return expected - actual — the value that is missing.

Because only one number is absent, the gap between the expected and actual totals is exactly that number. Using long keeps n * (n + 1) safe from int overflow for large N.

Dry Run

Walk through the example step by step

Finding the missing number in [1, 2, 4, 5]:

step                     | value
-------------------------+------
n = length + 1 = 4 + 1   | 5
expected = 5 * 6 / 2     | 15
actual = 1 + 2 + 4 + 5   | 12
missing = 15 - 12        | 3
--------------------------- answer = 3

Solution

Reveal the full Java solution
public class MissingNumber {
    public static int findMissing(int[] arr) {
        long n = arr.length + 1;
        long expected = n * (n + 1) / 2;
        long actual = 0;
        for (int x : arr) {
            actual += x;
        }
        return (int) (expected - actual);
    }

    public static void main(String[] args) {
        System.out.println(findMissing(new int[]{1, 2, 4, 5})); // 3
        System.out.println(findMissing(new int[]{2, 3, 1, 5})); // 4
    }
}

Since the array should hold every number from 1 to N but is missing one, the difference between the complete total N*(N+1)/2 and the actual total is precisely the missing value. This needs a single pass to sum the array and no extra storage. A long total prevents overflow when N is large, since N*(N+1) can exceed the int range.

Time: O(n)Space: O(1)

Common Mistakes

  • Using `N = arr.length` instead of `arr.length + 1`, which shifts the expected sum.
  • Computing the expected sum in `int`, overflowing for large N.
  • Sorting the array to hunt for a gap, which is O(n log n) and unnecessary.

Edge Cases to Test

  • The missing number is 1 (smallest), e.g. [2, 3, 4].
  • The missing number is N (largest), e.g. [1, 2, 3] with N = 4.
  • Very large N where the expected sum overflows a 32-bit int.

Interview Follow-Ups

  • How would you find the missing number using XOR to avoid any overflow risk?
  • How would you find two missing numbers instead of one?
  • How would you adapt this if the range started at 0 instead of 1?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us