Share my code: c++ O(n) time, O(1) space ,14line


  • 0
    B

    let's start withfor example :

    0 -- 0

    1 -- 1

    2 -- 10

    3 -- 11

    4 -- 1 00

    5 -- 1 01

    6 -- 1 10

    7 -- 1 11


    So:

    count of 1 in 1 is first1 + count of 1 in 0 (1%1)


    count of 1 in 2 is first1 + count of 1 in 1 (2%2)

    count of 1 in 3 is first1 + count of 1 in 2 (3%2)


    count of 1 in 4 is first1 + count of 1 in 0 (4%4)

    count of 1 in 5 is first1 + count of 1 in 1 (5%4)

    count of 1 in 6 is first1 + count of 1 in 2 (6%4)

    count of 1 in 7 is first1 + count of 1 in 3 (7%4)


    In summary :

    count of 1 in n is first1 + count of 1 in n%base (base is 1,2,4,8,16...)

    vector<int> countBits(int num) {
            vector<int> res;
            res.push_back(0);
            if(num == 0) return res;
            int base = 1 , count = 0;
            for(int i=1 ; i<=num ; i++){
                res.push_back(1 + res[i%base]);
                if(++count==base){
                    base *= 2;
                    count = 0;
                } 
            }
            return res;
        }

  • 0
    Z

    Come on, how come this is O(1) space? Even your return is O(n) space


  • 0
    Z

    Space complexity refers to extra space. It doesn't include necessary space of program such as input array or output vector.


Log in to reply
 

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