Problem
An array A[1..n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is ”fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?
Solution
Method 1 - Divide and Conquer approach for array having n=2^k - 1
Let’s assume for now that n is 2^k - 1 for some k.
Let’s also look at an example where k = 3.
000
001
010
011
100
101
110
111
You’ll notice that when there is a full set, like the one shown above, each column (each digit’s place) has the same number of ones and zeros. Of course, for convenience we are showing this as sorted, but in reality, I am not stating that it is.
Let’s take a look at the following list, where 101 is missing.
000
001
010
011
100
110
111
We look at the first bit of all of the elements ( O(n) ) and figure out which count is less than the other. We see that for the first bit, there is a number with the 1 in the most significant bit missing. This means that we know that our number has a one in its most significant bit. Basically, we partition into two sets, one where the most significant bit is 1 and one where the most significant bit is 0. The smaller set shows us what bit the missing number has.
We do the same thing on the smaller partition.
Since it is O(n) + O(n/2) + O (n/4) … it is basically O (2n) which is O (n).
Code
Java
public static int findMissing(List<Integer> array) {
return findMissing(array, Integer.SIZE - 1);
}
public static int findMissing(ArrayList<Integer> input, int column) {
if (column < 0) {
return 0;
}
List<Integer> oddIndices = new ArrayList<Integer>();
List<Integer> evenIndices = new ArrayList<Integer>();
for (Integer t: input) {
if ((t & (1<< column)) == 0) {
evenIndices.add(t);
} else {
oddIndices.add(t);
}
}
if (oddIndices.size() >= evenIndices.size()) {
return (findMissing(evenIndices, column - 1))<< 1 | 0;
} else {
return (findMissing(oddIndices, column - 1))<< 1 | 1;
}
}