Reference: LeetCode

Difficulty: Medium

## 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:**

1 | Input: 2 |

**Follow up:**

- It is very easy to come up with a solution with runtime $O(n \times \text{sizeof}(\text{int}))$. 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.

## Analysis

**Methods:**

Brute-Force

- For each value, count the number of bits.
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16public int[] countBits(int num) {

int[] ret = new int[num + 1];

for (int i = 0; i <= num; ++i) {

ret[i] = numberOfOneBits(i);

}

return ret;

}

private int numberOfOneBits(int n) {

int count = 0;

while (n != 0) {

count += 1;

n = n & (n - 1);

}

return count;

}**Time:**$O(NM)$. $M$ is the number of bits.**Space:**$O(N)$

- For each value, count the number of bits.
DP + Least Significant Bit

- We can observe that for a digit
`abcd`

in binary form, a transition function could be: `dp[abcd] = dp[abc] + dp[d] = dp[abc >>> 1] + (d & 1)`

.1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16// val binary #num

// 0 0 0 dp[0] = dp[00] = 0

// 1 1 1 dp[1] = dp[01] = 1

// 2 10 1 dp[2] = dp[10] = 1

// 3 11 2 dp[3] = dp[11] = 2 = dp[01] + dp[10] = 1 + 2

// 4 100 1 dp[4] = dp[100] = 1

// 5 101 2 dp[5] = dp[101] = 2 = dp[10] + dp[1]

// 6 110 2 dp[6] = dp[110] = 2 = dp[11] + dp[0]

// 7 111 3 dp[7] = dp[111] = 3 = dp[val >>> 1] + dp[val & 1]

public int[] countBits(int num) {

int[] dp = new int[num + 1];

for (int val = 0; val <= num; ++val) {

dp[val] = dp[val >>> 1] + (val & 1); // dp[val & 1]

}

return dp;

}**Time:**$O(N)$

**Space:**$O(N)$

- We can observe that for a digit
DP + Most Significant Bit

- I think this one is less elegant.
- Reference:link
1

2

3

4

5

6

7

8

9

10

11

12

13

14

15public int[] countBits(int num) {

int[] dp = new int[num + 1];

for (int i = 0; i <= num; ++i) {

int msb = locateMSB(i);

dp[i] = dp[i ^ msb] + ((msb > 0) ? 1 : 0); // turn off the msb

}

return dp;

}

public int locateMSB(int val) {

while ((val & (val - 1)) != 0) {

val &= (val - 1);

}

return val;

}**Time:**$O(N \times \text{sizeof}(int))$**Space:**$O(N)$

DP + Last Set Bit

- With the same logic as previous approaches, we can also do it with the last set bit. For
`x`

, we have: `dp[x] = dp[x & (x - 1)] + 1`

**Note:**loop should start from`1`

since`dp[0] = dp[0 & -1] + 1`

=`1`

.1

2

3

4

5

6

7public int[] countBits(int num) {

int[] dp = new int[num + 1];

for (int val = 1; val <= num; ++val) {

dp[val] = dp[val & (val - 1)] + 1;

}

return dp;

}**Time:**$O(N)$

**Space:**$O(N)$