3 ms O(n) time and O(1) space Java solution using DP Easy to understand and well explained


  • 2
    V
        /*
        0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
        0	1	1	2	1	2	2	3	1	2	2	3	2	3	3	4	1
        */    
        /*
         If we look at the series above it can be inferred that after each power of 2 (1, 2, 4,8, 16) each next
         number is the power of 2 plus the difference for example 5 = (4 +1), 6 = (4 + 2), ... 
         so number of ones in the bit will also be equal to number of bit bit in previous power of 2 
         (which is 1) plus the number of ones in number generated after difference. Hence it gives clue for 
         solving this problem using DP. put the base cases of 0, 1, 2 and then start adding number of ones 
         each index by adding from previous stored results. 
        */
            public int[] countBits(int num) {
                    int[] result = new int[num+1];
    
                    /*base condition starts*/
    
                    if(num == 0) return result;
                    result[1] = 1;
                    if(num == 1) return result;
                    result[2] = 1;
                    if(num == 2) return result;
    
                    /*base condition ends*/
    
                    int count = 1, start = 2; // initialize initial counters and start value
                    for(int i = 3; i < num + 1 ; i++){
                         /* if number is power of 2*/
                        if(count == start){  
                            result[i] = count = 1;
                            start = i;
                        }else{ // add the number of bits from previously calculated sequence
                            result[i] = result[count] + result[start];
                            count++;
                        }
                    }
                return result;
            }

Log in to reply
 

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