Find the minimal positive integer not occurring in a given sequence.

codility_MissingInteger.java

// you can also use imports, for example:
import java.util.*;

class Solution {
    public int solution(int[] A) {
        // search for max integer
        int max = 0;
        for (int a : A) {
            // skip negative integers
            if (a <= 0) { continue; }
            if (a > max) {
                max = a;
            }
        }
        
        int d = max > 0 ? log2n(max) + 1 : 1;
        //System.out.println("Max depth: " + d);
        ArrayList<HashSet<Integer>> B = new ArrayList<HashSet<Integer>>(d);
        for (int i = 0; i < d; i ++) {
            B.add(new HashSet<Integer>());
        }
        
        // setup a complete tree
        for (int j = 0; j < A.length; j ++) {
            // skip negative integers
            if (A[j] <= 0) { continue; }
            int curD = getDepth(A[j], d);
            //System.out.println("current depth: " + curD + ", " + A[j]);
            B.get(curD).add(A[j]);
        }
        
        // iterate the complete tree from leave level
        int min = 0;
        int totalLen = 0;
        for (int j = 0; j < B.size(); j ++) {
            int localLen = (int) Math.pow(2, d-j-1);
            //System.out.println("lvl #/size/count: " + j + "/" + B.get(j).size() + "/" + localLen);
            if (B.get(j).size() < localLen) {
                for (int i = totalLen+1; i < totalLen + localLen; i ++) {
                    if (!B.get(j).contains(i)) {
                        min = i;
                        break;
                    }
                }
                totalLen += localLen;
                break;
            } else {
                totalLen += localLen;
            }
        }
        
        // 1. no positive integers
        // 2. consecutive positive integers
        if (max == 0 || min == 0) {
            //System.out.println("min = max + 1: " + min);
            min = max + 1;
        }
        // print the tree
        // for (int i = 0; i < d; i ++) {
        //     for (int k : B.get(d-i-1)) {
        //         System.out.print(k + ",");
        //     }
        //     System.out.println();
        // }
        return min;
    }
    
    private int log2n(int n) {
        return (int) Math.floor( Math.log((double)n) / Math.log(2d) );
    }
    
    private int getDepth(int ele, int maxD) {
        int local = ele;
        int d = 0;
        int max_d = maxD;
        while (local > 0) {
            local = local - (int) Math.pow(2, --max_d);
            d ++;
        }
        return d-1;
    }
}