## 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;
}
};
``````