## 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.