Find two missing numbers from 1 to N

In the last post, I have mentioned that I want to write the solution for finding two missing numbers from 1 to N. It has been several months(almost half year, how time flies) and finally I have time to write it down.

Problem description:

Find two missing number from 1 to N

Given an array of size N-2, containing integer numbers from 1 to N, but there is two number missing. Return the missing number.

The difference of this problem to Find one missing number from 1 to N is that now we have two number missing. Now how can we solve this?

Analysis

Assuming the array given is A[] with length L, then we can easily know that $N = L + 2$, since there are two number missing in this array.

Brute Force

Of course, it’s very straight forward. You can use a boolean array B[] with size is N. Go through A[], for each number $n$, set B[n – 1] to true. In the end you will find there is only two places in B[] are false. Now you get it!

Time and space complexity: $O(N)$

Sum and Product

We can calculate the sum and product of each element in array A[], we can call it $S$ and $P$. And we know the sum and product of 1 to N, named $S_N$ and $P_N$. Assuming the missing numbers are $x$ and $y$, we have:

$x + y + S = S_N$

$x * y * P  = P_N$

There is only two unknown number in this equation set, it’s easy to calculate it.

Time complexity: $O(N)$

Space complexity: $O(1)$

Potential problem: When we calculate the product, it can overflow.

Sorting

Sorting is valid to solve this problem. However, the time complexity becomes $O(nlogn)$.

XOR

This method is highly recommended.

We assume that the missing numbers are $x$ and $y$.

We use a similar approach in problem Find one missing number from 1 to N. We do a XOR through all number in A[] and all number from 1 to N. But if we apply the same logic here, we only get an XOR of this two missing number, which is $Z = x XOR y$.

How can we get $x$ and $y$ separately? Since $x$ is not equal to $y$, $Z$ is not equal to $0$. So there must be one bit that is set in $Z$. For example ,if $x = 2 = 010_{(2)}$ and $y=4=100_{(2)}$, then $Z=110_{(2)}$. You can see there are two bit set in $Z$. The corresponding bit of these two missing number must be different at the bit that is set in $Z$. Why? Because $Z = x\ XOR\ y$. If there is a bit that is set in $Z$, the corresponding bit in $x$ and $y$ must be different to make it “1”.

We can pick any bit that is set in $Z$. To make it easy, we can just use the least significant bit, calling it mask $m$. Still using the example above, $m = Z \& (Z-1)=100_{(2)}$. It’s obvious that $m \& x != m$ while $m \& y = m$.

Then we can use the following logic to separate the number from 1 to N to two groups $X$ and $Y$: For any number $i$ from 1 to N, if $m \&  i \neq m$, then $i$ belongs to group $X$, otherwise, it belongs to group $Y$. Assuming the number is 1 to 5, and $m = 100_{(2)}$, we have:

$X: 1, 2, 3$

$Y: 4, 5$

Is this useful? Of course. When we get $m$, we can apply this logic for all numbers in A[], and all numbers from 1 to N. The group will be:

$X: 1, 3, 1, 2, 3 $

$Y: 5, 4, 5$

You can see that all number shows twice, except the missing numbers. And missing numbers are already separated to different groups. Now we can just do XOR for all numbers in group $X$ to get missing number $x$, and do XOR for all numbers in group $Y$ to get missing number $y$.

Actually, we don’t even need to save it to group. We can do XOR on the fly to save the space.

Time complexity: $O(N)$.

Space complexity: $O(1)$.

Code