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?

**My initial thoughts:**

I have no idea about this problem, basically. I thought that if the array is sorted, then the least significant bits of those integers would appear as 0, 1, 0, 1, 0, 1, etc. But the second least significant bits are then presented as 0, 0, 1, 1, 0, 0, 1, 1 and these two have to be corresponding to each other. Then I’m stack there.

**Solutions:**

public static int findMissing(ArrayList<Integer> array) {
return findMissing(array, Integer.SIZE - 1);
}
public static int findMissing(ArrayList<Integer> input, int column) {
if (column < 0) {
return 0;
}
ArrayList<Integer> oddIndices = new ArrayList<Integer>();
ArrayList<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;
}
}

The idea is to use recursion to process bit by bit from least significant to most significant. For each bit, the point is that if one value is missing, the number of 1s and 0s in this bit will change. Change how? Before removing an integer, we can only have three cases:

- Number of 1s = Number of 0s + 1.
- Number of 1s = Number of 0s.
- Number of 1s = Number of 0s – 1.

Therefore, if we remove an integer with LSB 1, we will end up with #1s = #0s. Hence, by counting the number of 1s and 0s of LSB, we can eliminate half of the integers and we advance to the second least significant bit. We continue to do this recursively until we find the missing value.

### Like this:

Like Loading...

*Related*

Shwetank Gupta

Aug 26, 2012@ 22:57:09Hi, Ruhne

I just debug your code, but I have a query, it seems that the output of ur code would the missing no. in reversed bit order.

for e.g. for input: 7, 2, 6, 4, 1, 5, 0 Output would be: 6 (110) and not 3 (011).

I think the recursion should move from LSB to MSB and not from MSB to LSB (ur case)

Reason: You are doing leftshift while returning from recursion so the bits would be appended in opposite order.

Correct me if I am wrong.

Runhe Tian

Aug 26, 2012@ 23:41:31Try this one:

Shwetank Gupta

Aug 27, 2012@ 01:26:31Hi Runhe

Thanks for the reply.

I have following things to comment:

1- We were supposed to implement this question using ‘ fetch bit ‘ functionality.

2- There is an error in your last logic:

I made the required changes in the code.

public class Solution {

public static int findMissing(int[] a) {

int i;

int x1 = a[1]; /* There is no a[0]…A[1..n] */

int x2 = 0; /* For XOR of all the elemets from 0 to n */

int n = a.length;

for (i = 2; i< n; i++)

x1 = x1^a[i];

for ( i = 0 i < n; i++)

x2 = x2^i; // numbers are from 0..n

return (x1^x2);

}

Nevertheless, this solution is not at accepted for the input question

Runhe Tian

Aug 27, 2012@ 01:36:561. The XOR operation can easily be implemented by fetch bit.

2. x2 is initialized to 0 so 0 has already been covered.