Find Missing Number in a Sequence in Java: 4 Methods (2026)

Introduction

Finding a missing number in a sequence is a classic problem that beautifully combines two concepts from earlier in this series — the Gauss sum formula for natural numbers, and the bitwise XOR operator's elegant self-canceling properties. Given an array containing n-1 distinct numbers from the range 1 to n, with exactly one number missing, the goal is to identify that missing value as efficiently as possible.

This guide covers the classic sum-based approach, the more robust XOR-based alternative (which avoids a subtle overflow risk the sum approach can encounter), a HashSet-based method, and an extension to find multiple missing numbers when more than one is absent from the sequence.

Understanding the Problem

Given an array like {1, 2, 4, 5, 6}, which should contain every number from 1 to 6 but is missing one, the task is to identify that missing value — in this case, 3.

This assumes the array contains n-1 distinct integers drawn from the range 1 to n, with exactly one value absent.

Method 1: Using the Sum Formula (Gauss Formula)

This approach leverages the Gauss formula covered earlier in this series: the expected sum of numbers from 1 to n is n × (n + 1) / 2. Subtracting the array's actual sum from this expected sum reveals the missing number.

public class MissingNumberSum {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6};
        int n = arr.length + 1;

        int expectedSum = n * (n + 1) / 2;
        int actualSum = 0;
        for (int num : arr) {
            actualSum += num;
        }

        int missingNumber = expectedSum - actualSum;
        System.out.println("Missing number: " + missingNumber);
    }
}

How this works

Since the array is missing exactly one number, its length is n-1, so:

n = arr.length + 1

The expectedSum (using the Gauss formula) represents what the sum should be if nothing were missing.

Subtracting the array's actualSum from this expected value isolates exactly the missing number, since every other number contributes equally to both the expected and actual totals, and only the missing one creates a difference.

Output

Missing number: 3

Method 2: Using the XOR Operator

A cleverer, overflow-resistant approach uses the bitwise XOR operator's key property:

• x ^ x = 0
• x ^ 0 = x

public class MissingNumberXOR {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6};
        int n = arr.length + 1;

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

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

        System.out.println("Missing number: " + xorAll);
    }
}

How this works

The first loop XORs together every number from 1 to n.

The second loop then XORs every number actually present in the array.

Since XOR-ing a value with itself cancels it out to 0, every number that appears in both the full range and the array cancels itself completely.

Only the missing number remains because it appears in the 1 to n sequence but never appears in the array to cancel itself.

Output

Missing number: 3

Method 3: Using a HashSet

A more intuitive, if slightly less elegant, approach checks which expected number is absent from a HashSet built from the array.

import java.util.HashSet;

public class MissingNumberHashSet {
    public static void main(String[] args) {
        int[] arr = {1, 2, 4, 5, 6};
        int n = arr.length + 1;

        HashSet<Integer> numberSet = new HashSet<>();
        for (int num : arr) {
            numberSet.add(num);
        }

        for (int i = 1; i <= n; i++) {
            if (!numberSet.contains(i)) {
                System.out.println("Missing number: " + i);
                break;
            }
        }
    }
}

How this works

Every array element is added to a HashSet.

Then each number from 1 to n is checked against that set.

The moment a number is found that is not present, it is identified as the missing value.

Output

Missing number: 3

Method 4: Finding Multiple Missing Numbers

A natural extension handles the case where more than one number might be missing from the sequence, using a boolean marker array to track which numbers were actually seen.

public class MultipleMissingNumbers {
    public static void main(String[] args) {
        int[] arr = {1, 3, 6, 4, 8};
        int n = 8;

        boolean[] present = new boolean[n + 1];
        for (int num : arr) {
            present[num] = true;
        }

        System.out.println("Missing numbers:");
        for (int i = 1; i <= n; i++) {
            if (!present[i]) {
                System.out.print(i + " ");
            }
        }
    }
}

Output

Missing numbers:
2 5 7

How this works

The present boolean array acts as a direct lookup table, indexed by the actual number values themselves.

present[num] = true;

marks every number found in the array.

Since neither the sum formula nor the XOR trick generalizes cleanly to finding multiple missing values (both are specifically designed around exactly one missing number), this marker-array approach is the standard technique whenever more than one number may be absent.

Why XOR Avoids the Overflow Risk That Sum Doesn't

Here's a genuinely important detail worth knowing: for very large values of n, the sum-based approach can overflow a standard 32-bit int, since n × (n + 1) / 2 grows quadratically with n.

For n around 100,000 or more, this calculation can exceed the safe int range, silently producing an incorrect result.

The XOR-based approach never has this problem, since XOR operations on 32-bit integers always produce a result that itself fits within 32 bits, regardless of how large the individual numbers being XORed together are.

This makes the XOR method a genuinely more robust choice for large sequences, even though the sum-based approach is often taught first for its more intuitive explanation.

How Java Handles This Internally (Memory Concept)

• In Methods 1 and 2, all variables (n, expectedSum, actualSum, xorAll) are primitive int values stored in stack memory, with no heap allocation needed at all. Both are genuinely O(1) extra space solutions.
• In Method 3, the HashSet<Integer> is heap-allocated, with each array element autoboxed into an Integer wrapper object before being added — resulting in O(n) extra space.
• In Method 4, the boolean[] present array is heap-allocated and sized to n + 1 to allow direct 1-indexed access without needing to subtract 1 from each number when using it as an array index.

Real-Life Analogy: Finding the Missing Ticket Number at a Raffle

Imagine a raffle where tickets are numbered sequentially from 1 to 100, and at the end of the event, you need to figure out which single ticket was never actually sold.

If you know the total value all 100 tickets should sum to (using the Gauss formula), and you calculate the actual sum of the tickets that were sold, the difference between those two totals tells you exactly which ticket number is missing — without ever needing to physically sort through and individually cross-check all 100 tickets against a master list.

Comparison Table of All Methods

Best Practices

• Prefer the XOR-based approach (Method 2) over the sum-based approach for genuinely large sequences, since it avoids the overflow risk entirely while maintaining the same O(n) time and O(1) space complexity.
• Use the sum formula (Method 1) for smaller, well-bounded sequences where its simpler, more intuitive explanation is preferred and overflow isn't a practical concern.
• Use a boolean marker array (Method 4) when more than one number might be missing, since both the sum and XOR tricks are specifically designed around exactly one missing value.
• Consider a HashSet (Method 3) when code clarity and intuitive readability matter more than minimizing memory usage.
• Always clarify with the interviewer or problem statement whether exactly one number is missing, since this assumption fundamentally shapes which technique is appropriate.

Common Mistakes Beginners Make

• Using the sum formula for very large n without considering overflow, silently producing an incorrect result once the expected sum exceeds the int range.
• Applying the single-missing-number sum or XOR trick when multiple numbers are actually missing, producing a meaningless or incorrect result, since these techniques are mathematically designed around exactly one missing value.
• Forgetting that n = arr.length + 1 when exactly one number is missing, using the array's raw length instead and miscalculating the expected range.
• Not understanding why XOR works, memorizing the technique without grasping the underlying x ^ x = 0 cancellation property, making it hard to adapt or explain the approach confidently.
• Using an unnecessarily large boolean array when the actual value range is much smaller than the array indices might suggest, wasting memory unnecessarily.

Expert Tips for Interviews

A strong, complete interview answer sounds like this:

"If exactly one number is missing from a sequence of 1 to n, I can find it using the Gauss sum formula — calculating the expected sum and subtracting the array's actual sum, which isolates the missing value. However, for very large n, this can risk integer overflow, so I'd prefer the XOR-based approach instead, which XORs together all numbers from 1 to n and all numbers in the array — every number that appears in both cancels out to zero, leaving only the missing number, without any overflow risk since XOR results always stay within the same bit width. If more than one number might be missing, I'd switch to a boolean marker array approach instead, since the sum and XOR techniques are specifically designed for exactly one missing value."

Proactively raising the overflow concern and explaining precisely why XOR avoids it demonstrates the kind of deeper numerical awareness that distinguishes a strong candidate on this specific, frequently asked question.

Pros and Cons

Sum Formula

Pros

• ✅ Simple, intuitive, easy to explain

Cons

• ❌ Risk of integer overflow for very large n

XOR

Pros

• ✅ O(1) space, no overflow risk, elegant

Cons

• ❌ Requires understanding XOR's cancellation property to explain confidently

HashSet

Pros

• ✅ Intuitive, easy to read and understand

Cons

• ❌ O(n) extra space, less impressive as an interview answer

Boolean Marker Array (Multiple Missing)

Pros

• ✅ Correctly generalizes to multiple missing numbers

Cons

• ❌ O(n) extra space; only applicable technique when more than one value is missing

Frequently Asked Questions

1. How do I find a missing number in a sequence from 1 to n in Java?

Calculate the expected sum using the Gauss formula n × (n + 1) / 2, subtract the array's actual sum, and the difference is the missing number.

2. Why should I use XOR instead of the sum formula to find a missing number?

XOR avoids the integer overflow risk that the sum formula can encounter for very large values of n, since XOR operations always produce results within the same bit width regardless of the numbers involved.

3. How does the XOR trick work for finding a missing number?

XOR-ing together every number from 1 to n, and then XOR-ing every number actually present in the array, causes every number in both sets to cancel out to zero, leaving only the missing number as the final result.

4. Can I find more than one missing number using the sum or XOR method?

No. Both techniques are specifically designed around exactly one missing number. For multiple missing numbers, use a boolean marker array instead to track which values were actually seen.

5. How do I find multiple missing numbers in a sequence in Java?

Create a boolean array indexed by the possible values, mark each number found in the input as present, then report every index that remains unmarked as a missing number.

6. What is the time complexity of finding a missing number using the sum formula or XOR?

O(n) for both approaches, since each requires a linear pass through the range and the array.

7. What is the space complexity of the sum and XOR approaches?

O(1) for both, since they use only a few primitive variables regardless of how large the sequence is.

8. Can I use a HashSet to find a missing number instead of the sum or XOR approach?

Yes. Add all array elements to a HashSet, then check every expected number from 1 to n against it. This approach works well but requires O(n) extra space compared to the O(1) space used by the sum and XOR methods.

9. Is finding a missing number in a sequence a common interview question?

Yes. It is one of the most common coding interview questions because it tests knowledge of mathematical reasoning, bitwise operations, and algorithm optimization.

10. What happens if the array contains duplicate values instead of being missing a number?

Both the sum and XOR techniques assume the array contains distinct values with exactly one missing number. If duplicates are present, these methods can produce incorrect or misleading results because their mathematical assumptions no longer hold.

11. How do I determine the value of n when using these techniques?

If the array is missing exactly one number from the range 1 to n, then:

n = arr.length + 1

because the array contains n − 1 elements.

12. Can this problem be extended to find a missing number in a sequence that doesn't start at 1?

Yes. You would need to adjust the expected sum (or XOR range) based on the actual starting and ending values of the sequence instead of assuming it always begins at 1.