Description of the problem:

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:

For `num = 5`

you should return `[0,1,1,2,1,2]`

.

Follow up:

- It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
- Space complexity should be O(n).
- Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

Credits:

Special thanks to @ syedee for adding this problem and creating all test cases.

The idea of solving the problem:

We can observe the binary form of numbers first.

0 ———>0

1 ———> 1

2 ———> 10

3 ———> 11

4 ———> 100

5———->1001

Binary for two to one, when the current number is 1, then move forward to 1..

In fact, we can find the form above.

When carried, repeat the process before proceeding until a new 1 is generated.

So we can continue to recycle the current RET array, the value of +1 in the RET array, and then add the tail of the RET array.

The count here represents the number to be calculated, so when count = num, the value of num has not yet been added.

When count > num, it has been added at this time.

Time complexity is O (n)

Space complexity is O (n)

Code:

class Solution { public: vector<int> countBits(int num) { vector<int> ret; ret.push_back(0); if(num == 0) return ret; ret.push_back(1); int count = 2; while(count <= num){ int last_end = ret.size(); for(int j = 0; j < last_end; j++){ ret.push_back(ret[j] + 1); count++; if(count > num) break; } } return ret; } };