Find Missing Number From a Given Array in Java

1. Overview

Finding the missing number from a specified range within an array in Java can be useful in various scenarios, such as data validation, ensuring completeness, or identifying gaps in a dataset.

In this tutorial, we’ll learn multiple approaches to finding a single missing number from an array in the integer range [1-N]. Additionally, we’ll also learn how to find all the missing numbers from an array.

2. Understanding the Scenario

Let’s imagine that we’ve got the numbers array with integers in the range [1-9], both inclusive:

int[] numbers = new int[] { 1, 4, 5, 2, 7, 8, 6, 9 };

Now, we aim to find the missing number from the array in the range [1-9].

To generalize the problem statement, we can compute the length of the array and set the upper bound, N:

int N = numbers.length + 1;

In the following sections, we’ll learn different ways to find the missing number from a given array in the range [1-N].

3. Using Arithmetic Sum

Let’s start by using arithmetic sum to find the missing number from the numbers array.

First, we’ll compute the expected sum of the arithmetic progression in the range [1-N] and the actual sum of the array:

int expectedSum = (N * (N + 1)) / 2;
int actualSum = Arrays.stream(numbers).sum();

Next, we can subtract the actualSum from the expectedSum to get the missingNumber:

int missingNumber = expectedSum - actualSum;

Lastly, let’s verify the result:

assertEquals(3, missingNumber);

It’s correct!

4. Using XOR Properties

Alternatively, we can use two interesting properties of the xor operator (^) to solve our use case:

• X^X = 0: When we xor a number with itself, we get zero.
• X^0 = X: When we xor a number with zero, we get the same number back.

First, we’ll do the xor operation on all the integer values in the closed range [1-9] using the reduce function:

int xorValue = IntStream.rangeClosed(1, N).reduce(0, (a, b) -> a ^ b);

We used 0 and (a, b) -> a ^ b, which is a lambda expression, as the identity and accumulator, respectively, for the reduce() operation.

Next, we’ll continue the xor operation with the integer values from the numbers array:

xorValue = Arrays.stream(numbers).reduce(xorValue, (x, y) -> x ^ y);

Since every number except the missing number comes twice, the xorValue will only contain the missing number in the numbers array from the range [1-9].

Lastly, we should verify that our approach gives the correct results:

assertEquals(3, xorValue);

Great! We got this one right.

5. Using Sorting

Our input array, numbers, is expected to contain all the consecutive values in the range [1-N], except for the missing number. So, if we sort the array, it’ll be convenient to spot the missing number where we don’t see a consecutive number.

First, let’s sort the numbers array:

Arrays.sort(numbers);

Next, we can iterate over the numbers array and check if the value at index is index+1 or not:

int missingNumber = -1;
for (int index = 0; index < numbers.length; index++) {
    if (numbers[index] != index + 1) {
        missingNumber = index + 1;
        break;
    }
}

When the condition fails, it implies that the expected value, index + 1, is missing from the array. So, we set the missingNumber and did an early exit from the loop.

Finally, let’s check that we’ve got the desired output:

assertEquals(3, missingNumber);

The result looks correct. However, we must note that we mutated the original input array in this case.

6. Tracking With a boolean Array

In the sorting approach, there were two major drawbacks:

• Overhead costs for sorting
• Mutation of the original input array

We can mitigate these issues by using a boolean array to keep track of the present numbers.

First, let’s define present as a boolean array of size N:

boolean[] present = new boolean[N];

We must recall that N was initialized as numbers.length + 1.

Next, we’ll iterate over the numbers array and mark the presence of each number in the present array:

int missingNumber = -1;
Arrays.stream(numbers).forEach(number -> present[number - 1] = true);

Further, we’ll perform another iteration, but on the present array, to find the number that’s not marked as present:

for (int index = 0; index < present.length; index++) {
    if (!present[index]) {
        missingNumber = index + 1;
        break;
    }
}

Lastly, let’s verify our approach by checking the value of the missingNumber variable:

assertEquals(3, missingNumber);

Perfect! Our approach worked. Further, we must note that we used additional space of N bytes as each boolean value will take 1 byte in Java.

7. Tracking With Bitset

We can optimize the space complexity by using Bitset over a boolean array.

BitSet bitSet = new BitSet(N);

With this initialization, we’ll use only enough space to represent N bits. It’s a considerable optimization when the value of N is quite high.

Next, let’s iterate over the numbers array and mark their presence by setting a bit at their position in bitset:

for (int num : numbers) {
    bitSet.set(num);
}

Now, we can find the missing number by checking the bit that’s not set:

int missingNumber = bitSet.nextClearBit(1);

Finally, let’s confirm that we’ve got the correct value in the missingNumber:

assertEquals(3, missingNumber);

Fantastic! It looks like we nailed this one.

8. Find All the Missing Numbers

To find multiple missing numbers, we can extend the solutions discussed in the earlier sections to find one missing number in the given array. For example, we can adapt the BitSet tracking approach with some modifications to handle multiple missing numbers.

First, let’s determine the maximum value in the given array. This maximum value establishes the upper bound ( N ) of the range from 1 to N:

int[] numbersWithMultipleMissing = new int[] { 1, 5, 2, 8, 9 };
int N = Arrays.stream(numbersWithMultipleMissing)
  .max()
  .getAsInt();

Next, let’s create allBitSet, which holds all the set bits from integer 1 to N:

BitSet allBitSet = new BitSet(N + 1);
IntStream.rangeClosed(1, N)
  .forEach(allBitSet::set);

Then, we can create presentBitSet, in which, we set bits for each number present in the numbersWithMultipleMissing array:

BitSet presentBitSet = new BitSet(N + 1);
Arrays.stream(numbersWithMultipleMissing)
  .forEach(presentBitSet::set);

Now, we can perform the logical AND operation between allBitSet and presentBitSet, which sets common bits in allBitSet and presentBitSet to true, while keeping the uncommon bits to false.

allBitSet.and(presentBitSet);

Finally, let’s iterate from 1 to N range and check all the unset bits in allBitSet. Each unset bit corresponds to a number that is missing from the range 1 to N:

List<Integer> result = IntStream.rangeClosed(1, N)
  .filter(i -> !allBitSet.get(i))
  .boxed()
  .sorted()
  .collect(Collectors.toList());

In the above logic, we collect all the missing numbers in the result list in sorted order. This ensures the result is compared to the expected output in a predictable sequence:

assertEquals(result, Arrays.asList(3, 4, 6, 7));

9. Conclusion

In this article, we learned how to find a missing number from an array. Further, we explored multiple ways to solve the use case, such as arithmetic sum, xor operations, sorting, and additional data structures, like Bitset and boolean array. Additionally, we also extend the logic to find multiple missing numbers from an array.