Exercise
There is an exercise in
Cracking the Code Interview.
Missing Two: You are given an array with all the numbers from 1 to N appearing exactly once,
except for one number that is missing. How can you find the missing number in O(N) time and
0( 1) space? What if there were two numbers missing?
The solution is quite simple, just sum up all numbers from 0 to N using well-known formula, then sum up all numbers in the table and the difference is the number missing.
In case of two numbers missing, this method gives back the sum of the numbers. So it is necessary to conduct additional calculation, for instance, to sum square of the numbers. This method we receive the sum of the squares of the missing number and after resolving quadratic formula, we come up with the numbers.
But this solution has a weak point. If the number is big enough, there is a risk of overflow and the whole calculation is wrong. The threshold is around the square root of the maximum value of the integer involved. For 32 bit integer, it is around 46341.
Alternative solution for one missing
The alternative solution for one number missing is to calculate the number of ones and zeros in a binary representation of all numbers and the same for the table with missing one. Comparing which bits are missing, we can reconstruct the number lost.
The C++ solution is available
here. Only number of ones should be calculated.
It does not break the time and space complexity requirement. Although we have to enumerate through bits for every number, the loop is still constant, 32 for 32 integer. 32*N is still O(N). Also, we need additional space for storing the number of bits but it is also constant and keeps O(1).
Solution for two missing
A similar solution can be applied to two numbers missing but only the sum can be reconstructed. If the difference between ones for the whole sum and the table is 0, it means that both missing numbers have zeros at the position. If the difference is 2, we can assume ones. But if the difference is 1, it means a combination of one and zero. Unfortunately, we cannot assign them to the numbers. But in case of the sum, it is not important because addition is commutative so we can assign them as we like.
uint ReconstructMissingSum(ByteCounter &all) const {
uint missing1 = 0;
uint missing2 = 0;
for (int i=BN-1; i>=0; i--) {
missing1 <<= 1;
missing2 <<= 1;
if (all.one_sum[i] != one_sum[i]) missing1 += 1;
// Sum have two ones at the position. Move the second 1 to the second number.
// We are calculating the sum, the order does not matter
if (all.one_sum[i] - one_sum[i] == 2) missing2 += 1;
}
// it is not the reconstruction of numbers but the sum only.
return missing1 + missing2;
}
But, as above, we need an additional equation to extract the exact values of the numbers. The same method can be applied for squares of the numbers. Unfortunately, this solution falls under the curse of overflow. Maybe there is a method to improve it but I was unable to find it so far.
