[Java] Find missing integer in array of unique elements

Given an array of length N of unique positive integers in range 0..N both inclusive, find the missing one.

We have two linear approaches, one uses a mathematical formula, the other some bit magic.

Math:

all numbers in range 0..N summed up can be calculated with the formula:

N * (N + 1) / 2

If we sum up all elements in the array, our missing number is the expected sum minus the actual sum

Bit:

if the array was of size N + 1 and all integers in range 0 .. N were present and sorted, each would sit at the index same as the number itself, for example:

idx: 0 1 2

num: 0 1 2

Since we know only one number is missing, there must be some index where the value doesn't match the index.

Since N + 1 is NOT a valid index in the array, we can initialize a variable to that, then XOR that variable with all values and indices in the array.

All repeated elements (index and value) would cancel out, leaving only the missing one as result.

You can check my implementation of findMissingNumber on my Gist (math) and Gist (bit) along with some tests in FindMissingNumberJTests (math) and FindMissingNumberJTests (bit).