Thursday, January 1, 2015

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;
 }

}

1 comment:

  1. The development of artificial intelligence (AI) has propelled more programming architects, information scientists, and different experts to investigate the plausibility of a vocation in machine learning. Notwithstanding, a few newcomers will in general spotlight a lot on hypothesis and insufficient on commonsense application. IEEE final year projects on machine learning In case you will succeed, you have to begin building machine learning projects in the near future.

    Projects assist you with improving your applied ML skills rapidly while allowing you to investigate an intriguing point. Furthermore, you can include projects into your portfolio, making it simpler to get a vocation, discover cool profession openings, and Final Year Project Centers in Chennai even arrange a more significant compensation.


    Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account.

    ReplyDelete