Java Program to Find Missing Number in Array (1 to N)

Finding the missing number in an array is a common Java programming interview question. The problem gives you an array containing numbers from 1 to N, but one number is missing. Your task is to identify that number.

For example, suppose an array contains {1, 2, 4, 5, 6}. The complete sequence should contain the numbers 1 through 6. Since 3 is missing, the expected result is 3.

You can solve this problem by checking every number in the expected range. However, there are more efficient approaches that do not require sorting or additional collections.

One solution uses the mathematical formula for the sum of the first N natural numbers. Another uses the bitwise XOR operator. Both approaches can find the missing number in linear time with constant extra space.

In this tutorial, I will explain how to find the missing number from an array containing numbers from 1 to N in Java. I will demonstrate the sum formula, XOR, and a simple search-based approach with complete programs and explanations.

Understanding the Missing Number Problem

Consider the following integer array:

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

The expected range is:

1, 2, 3, 4, 5, 6

The array does not contain 3.

Therefore:

Missing number: 3

Important Assumptions

The solutions in this tutorial assume the following:

• The expected numbers are from 1 to N, inclusive.
• Exactly one number is missing.
• All remaining numbers appear exactly once.
• Every array element belongs to the range from 1 to N.
• The array contains N - 1 elements.

The numbers do not need to be sorted.

These assumptions are important. If the array contains duplicate values or multiple missing numbers, the sum and XOR approaches may produce incorrect results.

Examples

Input Array	N	Missing Number
{1, 2, 4, 5}	5	3
{2, 3, 4, 5}	5	1
{1, 2, 3, 4}	5	5
{5, 1, 3, 2}	5	4
{}	1	1

Method 1: Find the Missing Number Using the Sum Formula

The simplest efficient solution uses the formula for the sum of the first N natural numbers.

The formula is:

Expected sum = N * (N + 1) / 2

This formula calculates the sum of all integers from 1 to N without using a loop.

Once you know the expected sum, calculate the sum of the elements actually present in the array.

The difference between the expected sum and the actual sum is the missing number.

Java Program

Create a Java class named MissingNumberUsingSum and add the following code:

import java.util.Arrays;
import java.util.Objects;

public class MissingNumberUsingSum {

    public static void main(String[] args) {

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

        int missingNumber = findMissingNumber(numbers);

        System.out.println("Array: " + Arrays.toString(numbers));
        System.out.println("Missing number: " + missingNumber);
    }

    /**
     * Finds the single missing number from the range 1 to N.
     *
     * Assumes the array contains N - 1 distinct values,
     * all belonging to the range 1 to N.
     *
     * @param numbers the input array
     * @return the missing number
     * @throws NullPointerException if the array is null
     */
    public static int findMissingNumber(int[] numbers) {

        Objects.requireNonNull(numbers, "Array must not be null");

        // The complete sequence contains one more element.
        long n = (long) numbers.length + 1;

        // Calculate the expected sum using long arithmetic
        // to avoid integer overflow.
        long expectedSum = n * (n + 1) / 2;

        long actualSum = 0;

        // Add the elements present in the array.
        for (int number : numbers) {
            actualSum += number;
        }

        // The difference is the missing number.
        return (int) (expectedSum - actualSum);
    }
}

Output

Array: [1, 2, 4, 5, 6]
Missing number: 3

How Does the Program Work?

The method receives an array containing five elements.

Since exactly one number is missing, the complete sequence should contain six numbers.

N = numbers.length + 1
N = 5 + 1
N = 6

The expected sum of numbers from 1 to 6 is:

Expected sum = 6 * (6 + 1) / 2
Expected sum = 6 * 7 / 2
Expected sum = 21

The actual sum of the array is:

Actual sum = 1 + 2 + 4 + 5 + 6
Actual sum = 18

The missing number is:

Missing number = Expected sum - Actual sum
Missing number = 21 - 18
Missing number = 3

The method returns 3.

Why Does the Program Use long?

The expression N * (N + 1) can exceed the maximum value of the Java int type for sufficiently large N.

Using long for the expected and actual sums prevents overflow for valid arrays within Java's supported array-size limits.

This is an important consideration when writing arithmetic algorithms in Java.

Method 2: Find the Missing Number Using XOR

Another efficient solution uses the bitwise XOR operator (^).

XOR has several useful properties:

• a ^ a = 0
• a ^ 0 = a
• a ^ b ^ a = b

When a value appears twice in an XOR expression, the two occurrences cancel each other.

This means you can XOR all numbers from 1 to N and all the values in the array. Every present number cancels out, leaving only the missing number.

Java Program

import java.util.Arrays;
import java.util.Objects;

public class MissingNumberUsingXor {

    public static void main(String[] args) {

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

        int missingNumber = findMissingNumber(numbers);

        System.out.println("Array: " + Arrays.toString(numbers));
        System.out.println("Missing number: " + missingNumber);
    }

    /**
     * Finds one missing number using the XOR operator.
     *
     * The array must contain N - 1 distinct values
     * from the range 1 to N.
     *
     * @param numbers the input array
     * @return the missing number
     * @throws NullPointerException if the array is null
     */
    public static int findMissingNumber(int[] numbers) {

        Objects.requireNonNull(numbers, "Array must not be null");

        if (numbers.length == Integer.MAX_VALUE) {
            throw new IllegalArgumentException(
                    "Array is too large for the int range."
            );
        }

        int n = numbers.length + 1;
        int xorResult = 0;

        // XOR every number from 1 to N.
        for (int number = 1; number <= n; number++) {
            xorResult ^= number;
        }

        // Cancel the numbers present in the array.
        for (int number : numbers) {
            xorResult ^= number;
        }

        return xorResult;
    }
}

Output

Array: [1, 2, 4, 5, 6]
Missing number: 3

How Does XOR Find the Missing Number?

The expected sequence is:

1, 2, 3, 4, 5, 6

The array contains:

1, 2, 4, 5, 6

The XOR expression is:

(1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6)
^
(1 ^ 2 ^ 4 ^ 5 ^ 6)

Every number except 3 appears twice.

Because XOR cancels equal values, the expression simplifies to:

3

Therefore, the missing number is 3.

The XOR approach avoids arithmetic sum overflow and uses constant extra space.

Method 3: Find the Missing Number Using a Simple Search

A beginner-friendly alternative is to check every expected number from 1 to N and search for it in the array.

If a number is not found, it is the missing number.

This approach is straightforward but less efficient because it may scan the array repeatedly.

Java Program

import java.util.Arrays;
import java.util.Objects;

public class MissingNumberUsingSearch {

    public static void main(String[] args) {

        int[] numbers = {1, 2, 4, 5};

        int missingNumber = findMissingNumber(numbers);

        System.out.println("Array: " + Arrays.toString(numbers));
        System.out.println("Missing number: " + missingNumber);
    }

    /**
     * Finds the missing number by searching for
     * every expected value.
     *
     * @param numbers an array containing N - 1 distinct
     *                values from 1 to N
     * @return the missing number
     */
    public static int findMissingNumber(int[] numbers) {

        Objects.requireNonNull(numbers, "Array must not be null");

        int n = numbers.length + 1;

        // Check every expected value from 1 to N.
        for (int expected = 1; expected <= n; expected++) {

            boolean found = false;

            // Search for the expected value.
            for (int number : numbers) {

                if (number == expected) {
                    found = true;
                    break;
                }
            }

            if (!found) {
                return expected;
            }
        }

        throw new IllegalArgumentException(
                "The input does not satisfy the problem requirements."
        );
    }
}

Output

Array: [1, 2, 4, 5]
Missing number: 3

Explanation

The outer loop checks each expected number from 1 to N.

The inner loop searches the array for that value.

If the current expected value does not appear in the array, the method returns it as the missing number.

This method requires no additional collection, but its nested loops can make it slow for large arrays.

How to Run the Java Programs

You can run these examples using IntelliJ IDEA, Eclipse, Visual Studio Code, or the command line.

To run the sum-formula example:

1. Install a Java Development Kit (JDK).
2. Create a file named MissingNumberUsingSum.java.
3. Copy the code from Method 1 into the file.
4. Open a terminal in the folder containing the file.
5. Compile and run the program:

javac MissingNumberUsingSum.java
java MissingNumberUsingSum

For the other examples, save each class in a file matching its public class name.

Comparing the Three Approaches

The sum and XOR methods are more efficient than checking every possible number individually.

Approach	Time Complexity	Extra Space
Sum formula	O(n)	O(1)
XOR	O(n)	O(1)
Simple search	O(n²)	O(1)

Here, n represents the size of the expected sequence.

The sum formula is generally the easiest solution to explain in a Java interview.

The XOR approach is also efficient and is useful when an interviewer wants to test your understanding of bitwise operations.

Important Edge Cases

The following test cases demonstrate how the algorithms behave when the missing number appears at different positions in the expected sequence.

Input Array	N	Expected Result
{2, 3, 4, 5}	5	1
{1, 2, 3, 4}	5	5
{1, 3}	3	2
{}	1	1
{4, 2, 1}	4	3

All three approaches can handle these cases under the stated assumptions.

Common Mistakes When Finding the Missing Number

1. Using the Wrong Value of N

If the array contains exactly one missing number from the range 1 to N, its length is N - 1.

Therefore:

N = array.length + 1

Using array.length directly as N produces an incorrect expected sum.

2. Ignoring Integer Overflow

The formula N * (N + 1) / 2 can overflow if calculated using int.

Use long arithmetic for the expected and actual sums.

3. Assuming the Array Must Be Sorted

Neither the sum formula nor the XOR approach requires a sorted array.

Both methods work with values in any order, provided the array satisfies the problem requirements.

4. Ignoring Duplicate Values

These solutions assume every present number appears exactly once.

For example, an array containing duplicate values may produce a misleading answer when using the sum formula or XOR.

If duplicates are allowed, the problem requires additional rules and validation.

5. Assuming the Methods Validate Every Input

The examples demonstrate algorithms for the standard interview problem. They do not fully verify that every array element is unique and within the expected range.

In production code, validate these conditions when the input cannot be trusted.

Frequently Asked Questions

How do you find a missing number in a Java array?

Calculate the expected sum of numbers from 1 to N using N * (N + 1) / 2. Subtract the sum of the array elements. The difference is the missing number.

Can I find the missing number without sorting the array?

Yes. Both the sum formula and XOR approaches work with unsorted arrays.

What is the time complexity of finding a missing number?

The sum formula and XOR solutions take O(n) time and use O(1) extra space.

Can XOR be used to find the missing number?

Yes. XOR all numbers from 1 to N and all elements in the array. Equal values cancel each other, leaving the missing number.

What if the array contains duplicate values?

The standard sum and XOR algorithms may return incorrect results if duplicates are present. You need a different approach or additional validation if duplicates are allowed.

What if more than one number is missing?

The algorithms in this tutorial assume exactly one missing number. Finding multiple missing numbers requires a different solution, such as tracking present values with a boolean array or a set.

Which approach is best for Java coding interviews?

The sum formula is a good starting point because it is easy to understand and explain. The XOR approach is also worth practicing because it demonstrates knowledge of bitwise operations.

Conclusion

In this tutorial, you learned how to find the missing number from an array containing numbers from 1 to N in Java.

The sum formula provides a simple and efficient solution. It calculates the expected total and subtracts the sum of the available elements. The XOR approach solves the same problem using bitwise operations without relying on arithmetic sums.

Both approaches run in linear time and use constant extra space. They also work without sorting the array.

For Java coding interviews, I recommend learning the sum-formula approach first and then practicing XOR. Once you understand these techniques, try related problems such as finding multiple missing numbers, identifying a duplicate and a missing number, and finding a missing value in a sequence from 0 to N.

Official Java Documentation

For more information about Java arrays and the operators used in this tutorial, refer to the following official Oracle documentation:

• Java Language Specification: Expressions — Explains arithmetic and bitwise XOR operators.
• Java Language Specification: Arrays — Explains arrays, indexing, and array length.
• Java Arrays Class — Documentation for array utility methods.
• Java Integer Class — Documentation for the int type and its supported range.
• Java Long Class — Documentation for the long type used to prevent arithmetic overflow.

Continue Learning with Java Guides

Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.

Explore My Udemy Courses View Developer Roadmaps

By Ramesh Fadatare - Udemy Instructor Partner