Career cup 5.7

FindMissingNumber.java

package Chapter5;

import java.util.ArrayList;
import java.util.List;

public class FindMissingNumber {
    
    public static final int INTEGER_SIZE = 32;
    public static int findMissingNumber(ArrayList<Integer> numbers) {
	return findMissingBit(numbers, 0);
    }

    private static int findMissingBit(List<Integer> numbers, int bitPos) {
	// TODO Auto-generated method stub
	if (bitPos == INTEGER_SIZE)
	    return 0;
	
	List<Integer> numsEndWithZero= new ArrayList<>();
	List<Integer> numsEndWithOne= new ArrayList<>();
	
	for (int i = 0; i < numbers.size(); i++) {
	    if(fetch(numbers, i, bitPos) == 0)
		numsEndWithZero.add(numbers.get(i));
	    else
		numsEndWithOne.add(numbers.get(i));
	}
	
	if(numsEndWithZero.size() <= numsEndWithOne.size())
	    //missing number has bit 0 in bitPos's bit
	    return ((findMissingBit(numsEndWithZero, bitPos+1) << 1) | 0);
	else
	    //missing number has bit 1 in bitPos's bit
	    return ((findMissingBit(numsEndWithOne, bitPos+1) << 1) | 1);
    }

    //fetch j'th bits of i'th number in array numbers
    private static int fetch(List<Integer> numbers, int i, int j) {
	int m = 1;
	while(j > 0) {
	    m *= 2;
	    j--;
	}
	
	return ((numbers.get(i)) / m) % 2 ;
    }
    
    public static void main(String[] args) {
	ArrayList<Integer> test = new ArrayList<>();
	for(int i = 0; i < 11; i++) {
	    if(i != 7)
		test.add(i);
	}
	System.out.println(findMissingNumber(test));
    }
}