## Problem

**Problem ID**: 338

**Title**: Counting Bits

**Difficulty**: Easy

**Description**:
Given an integer `n`

, return an array ans of length `n + 1`

such that for each
`i (0 <= i <= n)`

, `ans[i]`

is the number of 1’s in the binary representation of `i`

.

## Thoughts

Even though this question is LC easy question, I was not able to derive the most
optimal solution without looking at the solution. Admittedly, I was intellectually
lazy to push myself to think of the most optimal solution and went with the naive
solution of counting the number of bits for each number using `while(num > 0){num = num & (num-1);}`

method.

## Solution

The number of set bit for `i`

is either equal to the number of set bit of `i/2`

if
`i`

is even else it is 1 more than the number of set bit of `i-1`

. With this information
we can easily derive the following dp solution.

### Implementation

```
class Solution {
public:
vector<int> countBits(int n) {
vector<int>ans;
ans.push_back(0);
for (int i = 1; i <= n; i++) {
if (i&1) {
ans.push_back(ans[i-1] + 1);
} else {
ans.push_back(ans[i/2]);
}
}
return ans;
}
};
```