[Java] Find two missing numbers in array

Given an array of distinct integers in range 1..N and of length N-2 find the two missing numbers.

The O(N) time and space solution should be obvious, we can also use O(1) space if we spend O(NlogN) time sorting the input first.

However, there is a nice bit magic we can do to have a O(N) and O(1) space solution which involves the almighty XOR and the magic formula:

XOR of all elements in range 1..N with all elements in array gives Z, which is XOR of missing numbers X,Y.

Since we have no duplicates and missing numbers are in range 1..N, we know X and Y cannot be equal, this means X will have a bit set in a place that Y hasn't otherwise XOR would be 0 since it sets a 1 in every place where the two bits are different.

We can get a set bit in Z with the magic formula:

z & ~(z - 1)

We can then divide the array in two sets of elements, those who have that bit set and those who don't as our two missing numbers will be part of only one of those sets.

We XOR all those elements together and also with all elements in range 1..N that also have the same bit set or not, the result of the two sets of XORs are X and Y.

For example:

input = 4,2,3 we are missing 1,5 in binary: 001, 101

a = xor of all numbers 1..5 is: 1

b = xor of all elements in the array is: 5

z is a XOR b = 4

since x,y cannot be the same number, they have for sure at least one different bit

we pick rightmost set bit in the xor: 4

a = xor of all numbers in range 1..5 with that bit set is: 0

b = xor of all numbers in range 1..5 with that bit NOT set is: 1

c = xor of all elements in array with that bit set is: 1

d = xor of all elements in array with that bit NOT set is: 4

x = a ^ c = 1

y = b ^ d = 5

You can check my implementation of findTwoMissingNumbers on my Gist along with some tests in MissingTwoNumbersInArrayJTests.