Hello,

The key of the problem is to reuse the value we have already calculated. It's not difficult to come up following 2 observations:

```
A. count[i] = count[turn_off_the_left_most_set_bit_of_i(i)] + 1;
```

or

```
B. count[i] = count[turn_off_the_right_most_set_bit_of_i(i)] + 1;
```

Both `count[turn_off_the_left_most_set_bit_of_i(i)]`

and `count[turn_off_the_right_most_set_bit_of_i(i)]`

are already calculated the time we want to calculate `count[i]`

, so the we are good to go.

```
inline int turn_off_the_left_most_set_bit_of_i(int i) {
return i - (1 << (int)log2(i));
}
inline int turn_off_the_right_most_set_bit_of_i(int i) {
return i & (i-1);
}
vector<int> countBits(int num) {
vector<int> count(num + 1, 0);
count[0] = 0;
for (int i = 1; i <= num; ++i) {
count[i] = count[turn_off_the_right_most_set_bit_of_i(i)] + 1;
}
return count;
}
```