How to Find the Missing Number in an Array (1 to n Series) in Java

Finding the missing number in a sequence from 1 to n is one of the most popular array problems in Java interviews. The array contains n - 1 distinct numbers, meaning exactly one number is missing from the sequence.

This problem has multiple efficient solutions. The Sum Formula (Gauss's Formula) offers a simple mathematical approach, while the XOR technique provides an equally efficient solution without any risk of integer overflow. You can also solve it using a boolean visited array, although it requires additional memory.

In this tutorial, you'll learn all three approaches, understand how they work internally, and know when each method should be used.

Advertisement

Problem Statement

Given the following array:

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

The numbers are taken from the range 1 to 5.

Find the missing number.

Output

 
Missing Number = 3
 

The simplest solution is to calculate the expected sum of numbers from 1 to n, subtract the actual sum of the array, and return the difference.

Example

 
public class Main {

    public static int findMissingNumber(int[] arr, int n) {

        int expectedSum = n * (n + 1) / 2;

        int actualSum = 0;

        for (int num : arr) {
            actualSum += num;
        }

        return expectedSum - actualSum;
    }

    public static void main(String[] args) {

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

        System.out.println(findMissingNumber(numbers, 5));
    }
}
 

Output

 
3
 

Explanation

The formula

 
n × (n + 1) / 2
 

calculates the sum of all integers from 1 to n.

Subtracting the sum of the given array reveals the missing number.

Time Complexity: O(n)

Space Complexity: O(1)

Method 2: XOR Trick

The XOR approach avoids arithmetic entirely.

Since:

 
x ^ x = 0

x ^ 0 = x
 

every number that appears twice cancels itself, leaving only the missing number.

Example

 
public class Main {

    public static int findMissingNumberXOR(int[] arr, int n) {

        int result = 0;

        for (int i = 1; i <= n; i++) {
            result ^= i;
        }

        for (int num : arr) {
            result ^= num;
        }

        return result;
    }

    public static void main(String[] args) {

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

        System.out.println(findMissingNumberXOR(numbers, 5));
    }
}
 

Output

 
3
 

Explanation

The algorithm performs two XOR operations:

  • XOR all numbers from 1 to n
  • XOR every element in the array

Duplicate values cancel each other.

Only the missing number remains.

Time Complexity: O(n)

Space Complexity: O(1)

Unlike the sum formula, this approach cannot overflow.

Method 3: Boolean Visited Array

Another intuitive solution is to keep track of every number that appears in the array.

Example

 
public class Main {

    public static int findMissingNumber(int[] arr, int n) {

        boolean[] visited = new boolean[n + 1];

        for (int num : arr) {
            visited[num] = true;
        }

        for (int i = 1; i <= n; i++) {

            if (!visited[i]) {
                return i;
            }
        }

        return -1;
    }

    public static void main(String[] args) {

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

        System.out.println(findMissingNumber(numbers, 5));
    }
}
 

Output

 
3
 

Explanation

The algorithm marks every number as visited.

The first unvisited index is the missing number.

Although simple, this method requires extra memory.

Time Complexity: O(n)

Space Complexity: O(n)

Handling Overflow with the Sum Formula

For very large values of n, this calculation:

 
n * (n + 1)
 

may exceed the maximum value of an int.

Use long instead.

Example

 
long expectedSum = (long) n * (n + 1) / 2;
 

This prevents integer overflow and ensures correct results.

The XOR approach naturally avoids this issue because it performs bitwise operations instead of arithmetic addition.

Step-by-Step Explanation

Sum Formula

Given:

 
Array = [1, 2, 4, 5]

n = 5
 

Expected sum:

 
5 × 6 / 2 = 15
 

Actual sum:

 
1 + 2 + 4 + 5 = 12
 

Difference:

 
15 - 12 = 3
 

Missing number:

 
3
 

XOR Method

Numbers from 1 to 5:

 
1 ^ 2 ^ 3 ^ 4 ^ 5
 

Array values:

 
1 ^ 2 ^ 4 ^ 5
 

Every common value cancels:

 
1 ^ 1 = 0

2 ^ 2 = 0

4 ^ 4 = 0

5 ^ 5 = 0
 

Remaining value:

 
3
 

Internal Working

Sum Formula

 
Expected Sum = 15

Actual Sum = 12

Missing = 15 - 12 = 3
 

XOR

 
1 ^ 2 ^ 3 ^ 4 ^ 5

^

1 ^ 2 ^ 4 ^ 5

↓

3
 

Both methods require only a few variables and do not depend on the order of the array elements.

Real-Life Analogy

Imagine raffle tickets numbered 1 to 100.

You know the total sum of all ticket numbers if every ticket is present.

If one ticket is missing, simply:

  • Add the numbers on the available tickets.
  • Subtract the total from the expected sum.

The difference immediately reveals the missing ticket number.

The XOR method achieves the same goal using bitwise cancellation instead of arithmetic.

Best Practices

  • Use the Sum Formula for simple and readable code.
  • Use long when applying the Sum Formula to large values of n.
  • Use the XOR technique when you want to avoid overflow completely.
  • Avoid the boolean-array approach unless simplicity is more important than memory usage.
  • Verify that exactly one number is missing before applying these algorithms.

Common Mistakes

1. Ignoring Integer Overflow

Using int for very large values of n may produce incorrect results.

Use long instead.

2. Incorrect Loop Range

The loop should iterate from:

 
1
 

to

 
n
 

not to n - 1.

3. Using These Methods for Multiple Missing Numbers

The Sum Formula and XOR techniques work only when exactly one number is missing.

4. Using a Boolean Array Unnecessarily

Although easy to understand, the boolean-array solution uses additional memory when simpler O(1)-space solutions are available.

Expert Tips

  • The Sum Formula is based on the famous mathematical observation attributed to Carl Friedrich Gauss.
  • The XOR method is often preferred in interviews because it naturally avoids overflow.
  • This problem is commonly extended into "Find All Missing Numbers," which requires different algorithms.
  • Understanding both mathematical and bitwise solutions demonstrates strong problem-solving skills.

Comparison Table

Method Time Complexity Space Complexity Overflow Risk
Sum Formula O(n) O(1) ⚠️ Yes (Use long)
XOR Trick O(n) O(1) ✅ None
Boolean Visited Array O(n) O(n) ✅ None

Frequently Asked Questions

1. What is the easiest way to find the missing number?

The Sum Formula is the simplest solution because it uses basic arithmetic and only requires one traversal of the array.

2. Can the Sum Formula overflow?

Yes. For very large values of n, use long instead of int for intermediate calculations.

3. Why is the XOR method preferred?

The XOR technique avoids integer overflow while still achieving O(n) time and O(1) extra space.

4. Can these methods find multiple missing numbers?

No. These approaches are designed for arrays containing exactly one missing value.

5. Does the array need to be sorted?

No. All three methods work correctly regardless of the order of the elements.

6. What happens if no number is missing?

The problem assumes exactly one number is missing. If every number is present, these methods will not produce a meaningful result for that scenario.

7. Which method uses the least memory?

Both the Sum Formula and XOR Trick use O(1) extra space.

The boolean-array approach requires O(n) extra space.

They are related array problems, but the objectives are different.

This problem identifies a missing value, while duplicate-number problems identify repeated values.