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].
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. Conclusion
In this tutorial, 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.
As always, the code from this article is available over on GitHub.
