Combination of Easy Bit Manipulation and Dynamic Programming

  • 1

    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];
        int k=0;
        for(int i=1;i<=num;i++){
            else {
        return res;


  • 0

    res[k] should be always 1.

  • 1

    @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.