Find the Missing Number in an Array in Java (Sum, XOR, BitSet)

To find the missing number in an array that holds the numbers 1 to n with one number missing, we subtract the sum of the array from the expected sum n(n + 1)/2, where n is the array length plus one. The difference is the missing number, and the array does not need to be sorted.

We meet the problem in coding interviews and in real data checks, such as finding a gap in invoice numbers, order IDs or the sequence numbers of messages from a queue.

The following example finds the missing ticket number with the findMissing() method from section 2.

int[] tickets = {1, 2, 4, 5, 6};
int missing = findMissing(tickets);                     // 3
int lastGone = findMissing(new int[] {1, 2, 3});        // 4
int unsorted = findMissing(new int[] {5, 1, 2, 4});     // 3

The method also works when the last number is the one that is missing and when the array is unsorted, which is where many published solutions fail. We cover why the formula needs long arithmetic, the XOR trick, binary search for sorted arrays, several missing numbers with a BitSet, and ranges that do not start at 1.

1. Why the Sum Formula Finds the Missing Number

The numbers from 1 to n always add up to n(n + 1)/2. For n = 6, that is 6 x 7 / 2 = 21. When one number is missing, the array adds up to 21 minus that number, so subtracting the actual sum from 21 gives the number back.

The key detail is n. The array has n – 1 elements, so n is array.length + 1. We must not take n from the largest or the last element, because the missing number can be n itself, and in that case the largest element is n – 1.

2. Find the Missing Number in an Array with the Sum Formula

The method computes the expected sum and the actual sum as long values and returns the difference. The loop adds each element once, so the method takes O(n) time and O(1) extra memory. All versions are in the Core-Java repository with a Java 25 demo.

static int findMissing(int[] a) {
    Objects.requireNonNull(a, "array");
    long n = a.length + 1L;
    long expected = n * (n + 1) / 2;
    long actual = 0;
    for (int value : a) {
        actual += value;
    }
    return (int) (expected - actual);
}

int fromEmpty = findMissing(new int[0]);   // 1
int nullInput = findMissing(null);         // NullPointerException: array

An empty array means that n is 1 and the only number, 1, is missing. For the sum of the array, we can also write Arrays.stream(a).asLongStream().sum(), which reads well but does the same work as the loop.

2.1. Integer Overflow in the int Version

Many published solutions compute the formula with int. The product n(n + 1) passes Integer.MAX_VALUE when n reaches 46,341, and Java wraps the result without an exception, so the method returns a wrong number.

int bigN = 46_341;
int wrongSum = bigN * (bigN + 1) / 2;          // -1073716337
long rightSum = bigN * (bigN + 1L) / 2;        // 1073767311

We compute the expected sum as a long, which is safe for every possible array length. The largest Java array has about 2³¹ elements, and n(n + 1)/2 for that n is around 2.3 x 10¹⁸, which is below Long.MAX_VALUE.

Another common bug is taking n from the last element. The array {1, 2, …, 11} with 12 missing gives an expected sum of 66 for n = 11, the same as the actual sum, so the result is 0 instead of 12.

3. Missing Number with XOR

The XOR operator ^ returns 0 for two equal values, and any value XOR 0 is the value itself. If we XOR all numbers from 1 to n with all elements of the array, every present number appears twice and cancels out, and only the missing number is left.

static int findMissingXor(int[] a) {
    int result = 0;
    for (int i = 0; i < a.length; i++) {
        result ^= (i + 1) ^ a[i];
    }
    return result ^ (a.length + 1);
}

int xorMissing = findMissingXor(new int[] {1, 2, 4, 5, 6});   // 3
int xorUnsorted = findMissingXor(new int[] {5, 1, 4, 3});     // 2
int cancel = 7 ^ 7;                                           // 0

The XOR version never overflows, because XOR works bit by bit and never produces a carry. It is also O(n) time and O(1) memory, so the choice between sum and XOR is mostly about which one the reader of our code understands faster.

4. Sorted Arrays and Binary Search

When the array is sorted, we can find the gap in O(log n) time. Before the gap, every element equals its index plus 1, and from the gap onward, every element equals its index plus 2. A binary search finds the first index where a[i] != i + 1, and the missing number is that index plus 1.

static int findMissingSorted(int[] a) {
    int low = 0;
    int high = a.length - 1;
    while (low <= high) {
        int mid = (low + high) >>> 1;
        if (a[mid] == mid + 1) {
            low = mid + 1;              // gap is to the right
        } else {
            high = mid - 1;             // gap is here or to the left
        }
    }
    return low + 1;
}

int sortedGap = findMissingSorted(new int[] {1, 2, 3, 5, 6, 7, 8});   // 4
int sortedLast = findMissingSorted(new int[] {1, 2, 3});              // 4
int sortedFirst = findMissingSorted(new int[] {2, 3, 4});             // 1

Sorting an unsorted array first costs O(n log n), which is slower than the sum or XOR approach, so binary search pays off only when the data is already sorted, for example IDs read from an indexed database column.

5. Finding Several Missing Numbers with BitSet

The sum and XOR tricks work only when one number is missing. For several missing numbers, we mark every present number in a BitSet and collect the positions that stay clear. A BitSet uses one bit per number, so a range of one million numbers needs about 125 KB.

static List<Integer> findAllMissing(int[] a, int low, int high) {
    BitSet seen = new BitSet(high - low + 1);
    for (int value : a) {
        if (value < low || value > high) {
            throw new IllegalArgumentException("Out of range: " + value);
        }
        seen.set(value - low);
    }
    List<Integer> missing = new ArrayList<>();
    for (int i = seen.nextClearBit(0); i <= high - low; i = seen.nextClearBit(i + 1)) {
        missing.add(i + low);
    }
    return missing;
}

List<Integer> gaps = findAllMissing(new int[] {1, 5, 2, 8, 9}, 1, 10);   // [3, 4, 6, 7, 10]
List<Integer> noGaps = findAllMissing(new int[] {3, 1, 2}, 1, 3);         // []
List<Integer> bad = findAllMissing(new int[] {1, 42}, 1, 10);             // IllegalArgumentException: Out of range: 42

The method takes the range as parameters instead of reading it from the array, so it also reports a missing first or last number, such as 10 in the first call. The same idea works with a boolean[] or a HashSet, which use more memory per number.

6. Ranges That Do Not Start at 1

Real sequences rarely start at 1. For a range from low to high with one missing number, the expected sum is (low + high) x count / 2, where count is high – low + 1. The caller passes both bounds, because the array alone cannot tell whether the first or the last number is missing.

static long findMissingInRange(int[] a, long low, long high) {
    long count = high - low + 1;
    long expected = (low + high) * count / 2;
    long actual = 0;
    for (int value : a) {
        actual += value;
    }
    return expected - actual;
}

int[] invoices = {1001, 1002, 1004, 1005};
long gapInvoice = findMissingInRange(invoices, 1001, 1005);   // 1003

Say an online shop numbers its invoices without gaps, as tax rules in many countries require, and the monthly export has 4,999 invoices for the numbers 20001 to 25000. The accountant needs the missing invoice number to find a cancelled or lost document. With one gap, findMissingInRange() answers in one pass, and with several gaps, findAllMissing() from section 5 lists all of them.

7. Sum vs XOR vs BitSet

All approaches for one missing number in an unsorted array run in O(n) time, so the differences are memory, overflow risk and what else each one can do. A Big O comparison alone does not separate them.

Approach	Time	Extra memory	Needs sorted input	Several missing numbers	Overflow risk
Sum formula with long	O(n)	O(1)	No	No	None for array sizes
Sum formula with int	O(n)	O(1)	No	No	Wrong from n = 46,341
XOR	O(n)	O(1)	No	No	None
Binary search	O(log n)	O(1)	Yes	No	None
Sort and scan	O(n log n)	O(1) to O(n)	Sorts a copy or the input	Yes	None
BitSet	O(n + range)	One bit per number	No	Yes	None

The sum and XOR approaches trust the input. If the array contains a duplicate or a number outside the range, both return a wrong number without an error.

int fromDuplicate = findMissing(new int[] {1, 1, 3});   // 5, but 2 and 4 are missing

When the data comes from outside our code, such as a file or an API, we validate it first, or we use the BitSet version, which rejects values outside the range and handles any number of gaps.

8. Missing Number FAQs

An interviewer who sees the sum formula tends to follow up with one of these questions.

8.1. How do we find the missing number in an unsorted array without sorting it?

We use the sum formula or XOR from section 2 and section 3. Neither depends on the order of the elements, and both run in O(n) time with O(1) memory.

8.2. Is XOR better than the sum formula?

Not by much. XOR cannot overflow, whereas the sum formula needs long arithmetic to be safe. Both make one pass over the array, so we pick the one that our team reads faster.

8.3. How do we find the missing number with Java 8 streams?

We compute the expected sum and subtract the stream sum, using long values.

int[] nums = {3, 1, 4};
long n = nums.length + 1L;
long streamMissing = n * (n + 1) / 2 - Arrays.stream(nums).asLongStream().sum();   // 2

8.4. What if the array contains duplicates?

The sum and XOR tricks return wrong results, as the last example in section 7 shows. We mark every value in a BitSet or a HashSet and report the numbers that were never marked.

9. Conclusion

For one missing number in 1 to n, we subtract the actual sum from n(n + 1)/2, with n equal to the array length plus 1 and the arithmetic in long. XOR gives the same answer without any overflow risk, and binary search finds the gap in O(log n) when the array is already sorted.

For several missing numbers, invalid input or ranges that start elsewhere, a BitSet with explicit bounds is the safest choice. It costs one bit per number in the range and reports every gap, including the first and the last number.

10. References

• BitSet (Java SE 25 API)
• IntStream.asLongStream() (Java SE 25 API)
• JLS 25, Integer Bitwise Operators
• JLS 25, Multiplication Operator

Happy Learning !!

Source Code on Github