C++ 5 lines, o(n) space, o(n) time


  • 0
    J
    0000	0
    ---------
    0001	1
    ---------
    0010	1
    0011	2
    ---------
    0100	1
    0101	2
    0110	2
    0111	3
    ---------
    1000	1
    1001	2
    1010	2
    1011	3
    1100	2
    1101	3
    1110	3
    1111	4
    
    ...
    

    I think you will surely find something ;)

    The code is blew:

    class Solution {
    public:
        vector<int> countBits(int num) {
    		vector<int> temp(1, 0);
    		for(int stepLen = 1; stepLen < num + 1; stepLen *= 2)
    			for(int j = 0; j < stepLen; ++j)
    				temp.push_back(temp[j] + 1);
    		return vector<int>(temp.begin(), temp.begin() + num + 1);
        }
    };

Log in to reply
 

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