JAVA O(n) O(1) space solution


  • 2
    O
    public int[] countBits(int num) {
            int[] res = new int[num+1];
            res[0] = 0;
            int max = 0;
            for(int i = 1; i <= num; i++){
                if(((i-1)&i) == 0){ // check if i is power of 2
                    res[i] = 1;
                    max = i; //mark the cloest power of 2;
                }else{
                    res[i] = res[max] + res[i-max];
                }
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.