A little "bit" of observation :)

- All powers of 2 have only one set bit.
- Every other number, x, has exactly one extra set bit than the number formed by subtracting the largest power of 2 lesser than x, from x.

Examples:

6 -> 110 , 2 -> 10 , subfactor = 4

14 -> 1110 , 6-> 110 , subfactor = 8

27-> 11011, 11 -> 1011 , subfactor = 16

31 -> 11111, 15 -> 1111, subfactor = 16

```
class Solution {
public:
vector<int> countBits(int num) {
vector<int> bits(num+1, 0);
int n = 1;
while (n <= num) {
bits[n] = 1;
n = 2 * n;
}
int subfactor = 2;
for (int i = 3; i <= num; i++) {
if (bits[i] == 0) {
bits[i] = bits[i - subfactor] + 1;
} else {
subfactor = i;
}
}
return bits;
}
};
```