Q5_7.java

package Chapter5;

import java.util.ArrayList;
import java.util.Arrays;

public class Q5_7{
	public static void main(String[] args){	
		int[] test = {6,1,2,3,4,5,11,7,8,9,15,0,16,14,12,10,13};
		int n = 17;
		System.out.println(getMiss(test,n));
	}
	static int getMiss(int[] test, int n) {
		if((n-test.length)!=0)
			return -1;
		int numberOfDigits =(int)(Math.log(n)/Math.log(2)) +1; 
		ArrayList<Integer> list = new ArrayList<Integer>();
		for(int i:test)
			list.add(i);
		return findOneBit(list, 0,numberOfDigits);			 
	}
	private static int findOneBit(ArrayList<Integer> list, int i,int numberOfDigits) {
		if(i>=numberOfDigits)
			return 0;
		ArrayList<Integer> zeroList = new ArrayList<Integer>();
		ArrayList<Integer> oneList = new ArrayList<Integer>();
		for(Integer x:list){
			int value = (int) x;
			if(((value>>i) &1)==1)
			//if(true)
				oneList.add(x);
			else zeroList.add(x);
		}
		if(oneList.size()<zeroList.size())
			return 2*findOneBit(oneList,i+1,numberOfDigits)+1;
		else return 2*findOneBit(zeroList,i+1,numberOfDigits);
	}	
	
}