Find missing integer in an array with only access to bits operation

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:

  1. Number of 1s = Number of 0s + 1.
  2. Number of 1s = Number of 0s.
  3. 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.

Advertisements

4 Comments (+add yours?)

  1. Shwetank Gupta
    Aug 26, 2012 @ 22:57:09

    Hi, 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.

    Reply

    • Runhe Tian
      Aug 26, 2012 @ 23:41:31

      Try this one:

      
      
      public class Solution {
          public static int findMissing(int[] a) {
          int i;
          int x1 = a[0]; /* For XOR of all the elemets in arary */
          int x2 = 0; /* For XOR of all the elemets from 0 to n */
          int n = a.length;
      
          for (i = 1; i< n; i++)
              x1 = x1^a[i];
                  
          for ( i = 1; i <= n; i++)
              x2 = x2^i;         
          
          return (x1^x2);
      }
      

      Reply

  2. Shwetank Gupta
    Aug 27, 2012 @ 01:26:31

    Hi 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

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: