4ms Java easy-understanding solution with explanations


  • 0

    The main idea is to use the already calculated results:

    • f = [0,1] as seed.
    • f[i] = f[i-k]+1, where k is the largest number such that k*2<=i

    Attached is my AC code:

     public int[] countBits(int num) {
        int times=1, i=2;
        int[] ret = new int[num+1];
        ret[0]=0;
        if(num==0) return ret;
        ret[1]=1;
        while(i<=num){
          if(times*2<=i) times*=2;
          ret[i] = ret[i-times]+1;
          i++;
        }
        return ret;
     }

Log in to reply
 

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