Java Program to Find Missing Number in Array

You can find the missing number in an array of size n containing numbers from 1 to n+1 by calculating the expected sum with int total = (n + 1) * (n + 2) / 2; and subtracting the sum of array elements from it.

Examples

Input[1, 2, 4, 5, 6]

Output3

Input[2, 3, 1, 5]

Output4

Input[1]

Output2

How to Think About It

Imagine you have numbers from 1 to n+1 but one number is missing in the array. First, find the sum of all numbers from 1 to n+1 using the formula sum = (n+1)*(n+2)/2. Then add all numbers in the array. The missing number is the difference between the total sum and the sum of array elements.

Algorithm

1

Calculate the expected total sum of numbers from 1 to n+1 using the formula.

2

Calculate the sum of all elements present in the array.

3

Subtract the array sum from the total sum to find the missing number.

4

Return the missing number.

Code

java

public class MissingNumber {
    public static int findMissing(int[] arr) {
        int n = arr.length;
        int total = (n + 1) * (n + 2) / 2;
        int sum = 0;
        for (int num : arr) {
            sum += num;
        }
        return total - sum;
    }

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

Output

Missing number is: 3

Dry Run

Let's trace the example array [1, 2, 4, 5, 6] through the code

1

Calculate total sum

Array length n = 5, total = (5 + 1) * (5 + 2) / 2 = 6 * 7 / 2 = 21

2

Sum array elements

Sum = 1 + 2 + 4 + 5 + 6 = 18

3

Find missing number

Missing number = total - sum = 21 - 18 = 3

Step	Value
Total sum	21
Sum of array	18
Missing number	3

Why This Works

Step 1: Calculate expected total

The formula (n+1)*(n+2)/2 gives the sum of numbers from 1 to n+1, which is the full range including the missing number.

Step 2: Sum array elements

Adding all elements in the array gives the sum of present numbers, missing the one number.

Step 3: Subtract to find missing

Subtracting the array sum from the total sum leaves the missing number because all others cancel out.

Alternative Approaches

Using XOR operation

java

public class MissingNumberXOR {
    public static int findMissing(int[] arr) {
        int n = arr.length + 1;
        int xor = 0;
        for (int i = 1; i <= n; i++) {
            xor ^= i;
        }
        for (int num : arr) {
            xor ^= num;
        }
        return xor;
    }

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

XOR approach uses bitwise operation and avoids overflow risk but is less intuitive for beginners.

Sorting and checking neighbors

java

import java.util.Arrays;
public class MissingNumberSort {
    public static int findMissing(int[] arr) {
        Arrays.sort(arr);
        for (int i = 0; i < arr.length - 1; i++) {
            if (arr[i + 1] != arr[i] + 1) {
                return arr[i] + 1;
            }
        }
        return arr[arr.length - 1] + 1;
    }

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

Sorting approach is easy to understand but slower (O(n log n)) and modifies the array.

Complexity: O(n) time, O(1) space

Time Complexity

The program loops once through the array to sum elements, so it runs in linear time O(n).

Space Complexity

It uses only a few extra variables, so space complexity is constant O(1).

Which Approach is Fastest?

The sum formula method is fastest and simplest; XOR is also O(n) but less intuitive; sorting is slower at O(n log n).

Approach	Time	Space	Best For
Sum formula	O(n)	O(1)	Simple and fast for integer ranges
XOR operation	O(n)	O(1)	Avoids overflow, uses bitwise logic
Sorting and checking	O(n log n)	O(1)	Easy to understand but slower