Find missing integer -- Bit manipulation

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?

I am not good at bit manipulation, and that's the reason every such problem becomes so interesting to me. This one, we need to implement a method for the very easy question: search a missing integer in an array. And no, no array traversal, only bit operation is allowed.

So, considering any array of integers that are in binary representations, what will it look like? 0s and 1s, right? Then, what will the least significant digit of numbers look like?

For any array, it will be like:

0 1 0 1 0 1

or

0 1 0 1 0 1 0

depending on if n is an odd number or even number. So from the above array, we can make a conclusion that the number of 0s in the array is always >= the number of 1s in the array.

Next, what will happen if an odd number is removed? The number of 1s will be strictly smaller than the number of 0s. And alternatively, if we remove an even number, the number of 1s will be >= the number of 0s.

Ok, now all we need to do is to separate the lists to 0s and 1s and check which one has the larger size.
If we have determined that 1 (0) is removed, we pretty much can get rid of half of the list. If 1 is removed, it definitely is an odd number so we only have to check the odd number list and alternatively if 0 is removed, we only need to look at the even number list.

The problem is almost solved. What's next? We move to the next digit! Yup, recursion.

So, what about complexity? Is it O(n)?

Well, let's see, at the beginning of the recursion, i.e., when we check the least significant digit, we go through the whole array, so it takes O(n) time. Then the next recursion, O(n/2) time since we only check half of the input array, and then.... yeah, you get it?

O(n) + O(n/2) + O(n/4) + ... =O(2n) = O(n).

A-ha!, it is O(n)!

public class BitInteger {
 public static final int INTEGER_SIZE = 32;
 private boolean[] bits;
 public BitInteger() {
  bits = new boolean[INTEGER_SIZE];
 }
 public BitInteger(int value) {
  bits = new boolean[INTEGER_SIZE];
  for (int j = 0; j < INTEGER_SIZE; j++) {
   if (((value >> j) & 1) == 1)
    bits[INTEGER_SIZE - 1 - j] = true;  
  }
 }
 public int fetch(int k) {
  if (bits[k])
   return 1;
  else
   return 0;
 }
 public void set (int k, int bitValue) {
  if (bitValue == 0)
   bits[k] = false;
  else
   bits[k] = true;
 }
 public void set (int k, char bitValue) {
  if (bitValue == '0')
   bits[k] = false;
  else
   bits[k] = true;
 }
 public void set(int k, boolean bitValue) {
  bits[k] = bitValue;
 }
 public void swapValues(BitInteger number) {
  for (int i = 0; i < INTEGER_SIZE; i++) {
   int tmp = number.fetch(i);
   number.set(i, this.fetch(i));
   this.set(i, tmp);
  }
 }
 public int toInt() {
  int number = 0;
  for (int j = INTEGER_SIZE - 1; j >= 0; j--) {
   number = number | fetch(j);
   if (j > 0)
    number = number << 1;
  }
  return number;
 }

}
public class FindMissing {
 public int findMissing(ArrayList input) {
  return theMissingNumber(input, BitInteger.INTEGER_SIZE - 1);
 }
 private int theMissingNumber(ArrayList input, int column) {
  if (column < 0)
   return 0;
  ArrayList oddIndices = new ArrayList ();
  ArrayList evenIndices = new ArrayList ();
  for (int i = 0; i < input.size(); i++) {
   if (input.get(i).fetch(column) == 0) 
    evenIndices.add(input.get(i));
   if (input.get(i).fetch(column) == 1)
    oddIndices.add(input.get(i));
  }
  if (evenIndices.size() > oddIndices.size()) 
   return (theMissingNumber(oddIndices, column - 1) << 1) | 1;
  else
   return (theMissingNumber(evenIndices, column - 1) << 1) | 0;
 }

}