O(n) solution in C++


  • 0
    S

    Every x=pow(2,n) where n>=1, count of 1 becomes 1. Number of ones then repeats the pattern from 0 to x-1 until x*2.

    0000 --> 0
    0001
    0010 --> 2
    0011
    0100 --->4
    0101
    0110
    0111
    1000 --->8

    vector<int> countBits(int num) {
            vector<int>ones(num+1);
            if(num>=0)ones[0] = 0;
            if(num>=1)ones[1] = 1;
            int power = 1;
            for(int i=2; i<=num; i*=2){
                
                int j=i;
                int curr = 0; //start from 0
                while(j<i*2 && j<=num){
                    ones[j] = 1 + ones[curr];
                    j++;
                    curr++;
                }    
            }
            return ones;
        }
    

Log in to reply
 

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