CODEWITHSUNDEEP
javabit-manipulation
Hurstoill52
Hurstoill52

Reputation: 9

Finding a Missing Integer in an Array of Integers

I was recently browsing through a coding book and came across this interesting problem.

An array A contains all the integers from 0 through 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 0(n) time?

What the book does is go through a three page process explaining how exactly this problem can be done efficiently. To be honest, it was a bit TL;DR for me, so I made my own solution and compared it to the book's. I'm just wondering whether my solution actually works or not (since it seems suspect that the book's answer can be so long and detailed when an easier solution can be drafted up in a matter of minutes).

This is the book's solution:

 1 public int findMissing(ArrayList<BitInteger> array) {
 2     /* Start from the least significant bit, and work our way up */
 3     return findMissing(array, 0);
 4 }
 5
 6 public int findMissing(ArrayList<BitInteger> input, int column) {
 7     if (column >= BitInteger.INTEGER_SIZE) { // We're done!
 8         return 0;
 9     }
10     ArrayList<BitInteger> oneBits =
11         new ArrayList<BitInteger>(input.size()/2);
12     ArrayList<BitInteger> zeroBits =
13         new ArrayList<BitInteger>(input.size()/2);
14
15     for (BitInteger t : input) {
16         if (t.fetch(column) == 0) {
17             zeroBits.add(t);
18         } else {
19             oneBits.add(t);
20         }
21     }
22     if (zeroBits. size() <= oneBits.size()) {
23         int v = findMissing(zeroBits, column + 1);
24         return (v « 1) | 0;
25     } else {
26         int v = findMissing(oneBits, column + 1);
27         return (v « 1) | 1;
28     }
29 }

My own solution, which to me appears to be the same O(n) time complexity but is done in place with O(1) space complexity, is much simpler. I define the "fetch" method as taking in two parameters. The first specifies the xth bit, and the second specifies index number. I went under the assumption that this method was given, since it was mentioned in the problem as such ("fetch the jth bit of A[i]"). Basically, I just check to see if the lowest bit alternates between 1 and 0 - that's all there is to it.

int findMissing(int[] arr) {
    int lowBit = fetch(0, 0); // fetch the 0th bit of arr[0]
    if(lowBit != 0) {
        return 0; // obviously, the array is not starting at 0, so 0 must be what is removed
    }
    int expectedNextBit = 1; // we expect the lowest bit to be 1
    for(int x = 1; x < arr.length; x++) {
        lowBit = fetch(0, x); // fetch the 0th bit (lowest) of arr[x]
        if(lowBit != expectedNextBit) {
            return x;
        }
        expectedNextBit = lowBit ^ 0x1;
    }
    return arr.length;
}

My question is - what's wrong with my own solution? I'm a sophomore CS undergrad, and the book is written by PhDs, so I highly doubt that my answer can actually be better than theirs.

Upvotes: 0

Views: 176

Answers (2)

greybeard
greybeard

Reputation: 2504

what's wrong with my own solution?

First thing that is wrong with your source code:
The source code presented does not state the task to accomplish.

There is no reason to special-case index 0 (and a good one not to do so: what if 0 == arr.length?).

findMissing() could just read:

/** In instance array <code>A</code> of unique <code>int</code>s
 * from 0 to <code>A.length</code> inclusive, return the missing one. */
int findMissing() {
    for (int x = 0 ; x < A.length ; x++)
        if ((x&1) != fetch(0, x)) // fetch the 0th bit (lowest) of arr[x]
            return x;

    return A.length;
}

Upvotes: 0

Russell Cohen
Russell Cohen

Reputation: 725

Your solution incorrectly assumes that the input numbers are sorted. If your input was [0, 2, 1, 3, 5] then your solution would incorrectly report 1 even though it appears later in the array.

Upvotes: 1

Related Questions