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[j]," which takes constant time. Write code to fin…

CC150-5.7.java

package POJ;

import java.util.ArrayList;

public class Main{
 
	/**
	 * 
	 * 5.7 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[j]," which takes constant time. Write code
	 * to find the missing integer. Can you do it in 0(n) time?
	 * 
	 * Solution:
	 * count(0s) <= count(1s) ，remove的是偶数，count(0s) > count(1s)，remove的是奇数。对LSB从后往前依次上述操作。
	 * 
	 */
	public static void main(String[] args) {
		Main so = new Main();
		ArrayList<Integer> array = new ArrayList<Integer>();
        for (int i = 0; i < 20; ++i) {
            if (i !=19 ) {
                array.add(i);
            }
        }
		System.out.println(so.missingBit(array));
	}

	private int missingBit(ArrayList<Integer> array) {
		// TODO Auto-generated method stub
		return findMissintBit(array,0);
	}

	private int findMissintBit(ArrayList<Integer> array, int bitNumber) {
		// TODO Auto-generated method stub
		if(array.size()==0||bitNumber>=32)
			return 0;
		
		ArrayList<Integer> odd=new ArrayList<Integer>(array.size()/2);
		ArrayList<Integer> even=new ArrayList<Integer>(array.size()/2);
		for(int i=0;i<array.size();i++){
			if(fetch(array,i,bitNumber)==1)
				odd.add(array.get(i));
			else
				even.add(array.get(i));
		}
		if(even.size()>odd.size()){
			return ((findMissintBit(odd, bitNumber+1))<<1|1);
		}else{
			//remove的是偶数
			return ((findMissintBit(even,bitNumber+1)<<1)|0);
		}
	}

	private int fetch(ArrayList<Integer> array, int i, int bitNumber) {
		// TODO Auto-generated method stub
		if(i<0||i>=array.size())
			return -1;
		return (array.get(i)&(1<<bitNumber))==0?0:1;
	}
	
}