Combination of Easy Bit Manipulation and Dynamic Programming


  • 1
    S

    First of all,by using the hint of this problem,we can find the conclusion easily that
    1 if the number is the power of two,it just has one'1' digit.
    2 other numbers' '1' digit are based on (their nearest number of two's power) +(number-its nearest number of two's power).

    For example, 15 can be the result of 8( nearest number of two's power)+7.We just need to remember its nearest number of power of 2.
    Then,the problem can solve itself!

    public class Solution {
    public int[] countBits(int num) {
        int [] res=new int[num+1];
        res[0]=0;
        int k=0;
        for(int i=1;i<=num;i++){
            if((i&(i-1))==0){
                k=i;
               res[i]=1; 
            }
            else {
                res[i]=res[k]+res[i-k];
            }
        }
        return res;
    }
    

    }


  • 0

    res[k] should be always 1.


  • 1
    S

    @nafSadh Yeah,you are right!
    So the res[k] in the else{} can be replaced by 1.
    Thank you for your reply!


Log in to reply
 

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