C++ solution , time O(n) , space O(n)


  • 4
    P
    class Solution {
    public:
            vector<int> countBits(int num) {
                int flag = 2;
    	        vector<int> res = { 0 };
    	        for (int i = 1; i <= num; i++){
    		        if (i >= flag)
    			        flag *= 2;
    		        res.push_back(res[i - flag/2] + 1);
    	        }
    	        return res;
            }
    };

  • 0
    K

    This actually meets my thought, better and cleaner than my implementation.


  • 0
    S

    Can you explain the logic used here?


  • 3
    W

    My easy c++ solution

    class Solution {
    public:
        vector<int> countBits(int num) {
            vector<int> res(num+1,0);
            for(int i=1;i<=num;i++)
                res[i]=res[i>>1]+(i&1);
            return res;
        }
    };

  • 0
    P

    write the binary represent of number 0~7, and you will find that lowbit of number 4~7 is same with number 0~3, and one "1" more than number 0~3 at highbit


Log in to reply
 

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