A C++ solution, with explanation


  • 0
    P
    /*
     *  a[2^i+k] = a[2^(i-1)+k], k<2^(i-1)
     *  a[2^i+2^(i-1)+k] = a[2^i+k]+1, k<2^(i-1)
    */
    
    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> bits(num+1, 0);
            bits[1] = 1;
            
            for(int range = 0b10; range <= num; range <<= 1){
                int j = range;//2^i
                int pre = range>>1;//2^(i-1)
                int next = range<<1;//2^(i+1)
                while( j < next && j <= num ){
                    if( j-range < pre )
                        bits[j] = bits[pre + j - range];
                    else
                        bits[j] = bits[j- pre] + 1;
                    j++;
                }
            }
            
            return bits;
        }
    };

Log in to reply
 

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