Approach
Observe that all powers of 2 have only a single 1 in their binary representation.
Decimal Binary
0 -> 00000
1 -> 00001
2 -> 00010
3 -> 00011
4 -> 00100
5 -> 00101
6 -> 00110
7 -> 00111
8 -> 01000
What is the easiest way to write the binary of numbers 9 to 15? We can write 9 as 8 + 1 and 15 as 8 + 7. 1 and 7 both being smaller than 8 will only require 3 bits whereas representing 8 requires 4 bits. So it is pretty simple to add 8 with any number less than 8 like this:
8: 1000
1: 0001
------
9: 1001
------
8: 1000
7: 0111
------
15: 1111
------
Note that number of ones are also adding up here. Number of ones in 15 = no. of 1s in 8 + no. of 1s in 7.
So all we have to do is define each number as a sum power of two just smaller than that number and the remainder. Let us define dp[i] as number of 1s in the binary representation of i. So the number of 1’s in binary representation of some number j = 2^k + r where 0=<r<2^k is dp[2^k] + dp[r].
/*
* number of 1s in binary of 2^i is always 1
* "prev" stores the 2^j number just smaller than the current number
* if we have the answer to dp[0..i-1], number of 1st in a number i will be 1 (for 2^j) + i-2^j
* consider the number 15. Power of 2 just smaller than 15 is 8. 15 - 8 = 7. So number of 1s in binary of 15 = 1 (as 8 introduces a new bit) + number of 1s in binary of 7 = 1 + 3 = 4
*/
vector<int> countBits(int num) {
if (num == 0)
return {0};
vector<int> dp(num+1, 0);
int prev = 1;
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i<=num; i++) {
if (i==prev*2) { // if i is the next power of 2 then it only has one 1 in its representation
dp[i] = 1;
prev*=2; // update prev to be the next power of 2
}
else
dp[i] = dp[prev] + dp[i-prev]; // here prev is the power of 2 just smaller than i
}
return dp;
}
Time complexity: O(n)
Space complexity: O(n)