Press "Enter" to skip to content
338. Counting Bits

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 1:

```Input: 2
Output: [0,1,1]```

Example 2:

```Input: 5
Output: `[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.

dp = 0;

dp = dp + 1;

dp = dp + 1;

dp = dp +1;

dp = dp + 1;

dp = dp + 1;

dp = dp + 1;

dp = dp + 1;

dp = dp + 1;

dp = 0;

dp = dp[1-1] + 1;

dp = dp[2-2] + 1;

dp = dp[3-2] +1;

dp = dp[4-4] + 1;

dp = dp[5-4] + 1;

dp = dp[6-4] + 1;

dp = dp[7-4] + 1;

dp = dp[8-8] + 1;

```public class CountingBits {
public static int[] countBits(int num) {
int[] res = new int[num + 1];
int i = 1;
int offset = 1;
while (i < num + 1) {
if (offset * 2 == i) {
offset = offset * 2;
}
res[i] = res[i - offset] + 1;
i++;
}
return res;
}

}```