[DP] Clear C++ 6 lines O(n) time&space one pass with explanation


  • 0

    Consider integer 8, binary: 1000
    dp[8]=1 (1000)
    dp[9]=1+dp[1]=1+1=2 (1001)
    dp[10]=1+dp[2]=1+1=2 (1010)
    dp[11]=1+dp[3]=1+2=3 (1011)
    ...
    dp[15]=1+dp[7]=1+3=4 (1111)
    Therefore, we find the pattern:
    dp[2^n]=1;
    dp[2^n+1]=1+dp[1];
    dp[2^n+2]=1+dp[2];
    dp[2^n+3]=1+dp[3];
    ...
    dp[2^(n+1)-1]=1+dp[2^n-1];
    dp[2^(n+1)]=1;
    ...
    Code:

        vector<int> countBits(int num) {
            vector<int>res(num+1,0);
            int j=1,k=2;
            for(int i=1;i<num+1;i++)
                if(i==k) res[i]=1,k*=2,j=1;
                else res[i]=1+res[j++];
            return res;
        }
    

Log in to reply
 

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