public class Solution {

```
public int[] countBits(int num) {
```

// Initialize dp array of length num.length + 1

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

// dp[0] is initialized as 0

// If i is even then number of bits is same as i/2

// Else if i is odd then number of bits is +1 as that of i/2

```
for (int i = 1 ; i <= num ; i++) {
if (i % 2 == 0) {
dp[i] = dp[i/2];
} else {
dp[i] = dp[i/2] + 1;
}
}
return dp;
}
```

}