Question5_7.java

import java.util.ArrayList;

/**
 * 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 j-th bit of A[i]",
 * which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?
 * 
 * Time  Complexity: O(n)
 * Space Complexity: O(logn)
 */

public class Question5_7 {
    public int missingElement(ArrayList<Integer> array) {
        return recMissingElement(array, 0);
    }
    
    
    private int recMissingElement(ArrayList<Integer> array, int bit) {
        if (array.size() == 0 || bit >= 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, bit) == 1) {
                odd.add(array.get(i));
            } else {
                even.add(array.get(i));
            }
        }
        
        if (even.size() > odd.size()) {
            return recMissingElement(odd, bit + 1) << 1 | 1;
        } else {
            return recMissingElement(even, bit + 1) << 1 | 0;
        }
    }
    
    
    private int fetch(ArrayList<Integer> array, int i, int j) {
        if (i < 0 || i >= array.size()) {
            return -1;
        }
        
        return (array.get(i) & (1 << j)) == 0 ? 0 : 1;
    }
    
    
    public static void main(String[] args) {
        Question5_7 question5_7 = new Question5_7();
        ArrayList<Integer> array = new ArrayList<Integer>();
        for (int i = 0; i < 10; ++i) {
            if (i != 6) {
                array.add(i);
            }
        }
        System.out.println(question5_7.missingElement(array));
    }
}