## Friday, July 8, 2016

### Missing Number - Cracking the coding interview

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?

``````int get(int a[], int i){
int ret = 0;
for(int j=31; j>=0; --j)
ret = (ret << 1) | fetch(a, i, j);
return ret;
}
``````

``````int missing(int a[], int n){
bool *b = new bool[n+1];
memset(b, false, (n+1)*sizeof(bool));
for(int i=0; i<n; ++i)
b[get(a, i)] = true;
for(int i=0; i<n+1; ++i){
if(!b[i]) return i;
}
delete[] b;
}
``````

``````int get1(int a[], int i){
int ret = 0;
int base = 32*i;
for(int j=base+31; j>=base; --j)
ret = (ret << 1) | fetch1(a, j);
return ret;
}
``````

``` public static int fetch(int a[],int i,int j){
return (a[i]>>j)&1;
}
public static int get(int[] a ,int i){
int result = 0 ;
for(int j=31;j>=0;--j){
result = result<<1|fetch(a,i,j);
}
return result ;
}```
public class BitInteger {
public static int INTEGER_SIZE;
private boolean[] bits;
public BitInteger() {
bits = new boolean[INTEGER_SIZE];
}
/* Creates a number equal to given value. Takes time proportional
* to 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;
else bits[INTEGER_SIZE - 1 - j] = false;
}
}
/** Returns k-th most-significant bit. */
public int fetch(int k){
if (bits[k]) return 1;
else return 0;
}
/** Sets k-th most-significant bit. */
public void set(int k, int bitValue){
if (bitValue == 0 ) bits[k] = false;
else bits[k] = true;
}
/** Sets k-th most-significant bit. */
public void set(int k, char bitValue){
if (bitValue == '0' ) bits[k] = false;
else bits[k] = true;
}
/** Sets k-th most-significant bit. */
public void set(int k, boolean bitValue){
bits[k] = bitValue;
}
public void swapValues(BitInteger number) {
for (int i = 0; i < INTEGER_SIZE; i++) {
int temp = number.fetch(i);
number.set(i, this.fetch(i));
this.set(i, temp);
}
}
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;
}
}

/* Create a random array of numbers from 0 to n, but skip 'missing' */
public static ArrayList<BitInteger> initialize(int n, int missing) {
BitInteger.INTEGER_SIZE = Integer.toBinaryString(n).length();
ArrayList<BitInteger> array = new ArrayList<BitInteger>();

for (int i = 1; i <= n; i++) {
array.add(new BitInteger(i == missing ? 0 : i));
}

// Shuffle the array once.
for (int i = 0; i < n; i++){
int rand = i + (int) (Math.random() * (n-i));
array.get(i).swapValues(array.get(rand));
}

return array;
}

public static int findMissing(ArrayList<BitInteger> array) {
return findMissing(array, BitInteger.INTEGER_SIZE - 1);
}

private static int findMissing(ArrayList<BitInteger> input, int column) {
if (column < 0) { // Base case and error condition
return 0;
}
ArrayList<BitInteger> oneBits = new ArrayList<BitInteger>(input.size()/2);
ArrayList<BitInteger> zeroBits = new ArrayList<BitInteger>(input.size()/2);
for (BitInteger t : input) {
if (t.fetch(column) == 0) {
} else {
}
}
if (zeroBits.size() <= oneBits.size()) {
int v = findMissing(zeroBits, column - 1);
System.out.print("0");
return (v << 1) | 0;
} else {
int v = findMissing(oneBits, column - 1);
System.out.print("1");
return (v << 1) | 1;
}
}