CareerCup 150

CC 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 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
 *
 * @author Garden
 */
public class CC5_7 {

    public static int findMissing(ArrayList<Integer> array, int bit) {
        if (array.size() == 0 || bit >= 32) {
            return 0;
        }

        ArrayList<Integer> oneBits = new ArrayList<Integer>(array.size() / 2);
        ArrayList<Integer> zeroBits = new ArrayList<Integer>(array.size() / 2);

        for (int i = 0; i < array.size(); ++i) {
            if (fetch(array, i, bit) == 1) {
                oneBits.add(array.get(i));
            } else {
                zeroBits.add(array.get(i));
            }
        }

        if (oneBits.size() >= zeroBits.size()) {
            int v = findMissing(zeroBits, bit + 1) << 1;
            System.out.println(v);
            return v | 0;
        } else {
            int v = findMissing(oneBits, bit + 1) << 1;
            System.out.println(v);
            return v | 1;
        }
    }

    private static int fetch(ArrayList<Integer> array, int i, int j) {
        if (i < 0 || i >= array.size()) {
            return -1;
        }

        //当前位置是否是1
        return (array.get(i) & (1 << j)) == 0 ? 0 : 1;
    }

    public static void main(String[] args) {
        int num = 9;
        int remove = 5;
        ArrayList<Integer> array = new ArrayList();

        for (int i = 0; i < num; i++) {
            if (i != remove) {
                array.add(i);
            }
        }

        int x = findMissing(array, 0);
        System.out.println(x);
    }
}

如果n是奇数，0s bit 和1s bit的数字相同，count(0s) = count(1s) 。 n是偶数， 0s bit 比 1s bit多一个 count(0s) = count(1s) + 1
当n是奇数时候，如果remove了一个奇数，则一个0移除，count(0s) = count(1s) 。remove一个偶数，一个1移除，count(0s) > count(1s)。
当n是偶数时候，如果remove了一个奇数，则一个0移除，count(0s) < count(1s)。 remove一个偶数，一个1移除，count(0s) > count(1s) 。
所以，count(0s) <= count(1s) ，remove的是奇数，count(0s) > count(1s)，remove的是偶数。

对LSB从后往前依次上述操作。