<h4 id="heading-given-an-integer-n-return-an-array-ans-of-length-n-1-such-that-for-each-i-0">Given an integer n, return an array ans of length n + 1 such that for each i (0 &lt;= i &lt;= n), ans[i] is the number of 1's in the binary representation of i.</h4>
<hr />

Example 1: 
Input: n = 2 
Output: [0,1,1] 
Explanation: 
0 --&gt; 0 
1 --&gt; 1 
2 --&gt; 10
Example 2: 
Input: n = 5 
Output: [0,1,1,2,1,2] 
Explanation: 
0 --&gt; 0 
1 --&gt; 1 
2 --&gt; 10 
3 --&gt; 11 
4 --&gt; 100 
5 --&gt; 101 
<hr />


<pre><code>class Solution:
 def countBits(self, n: int) -&gt; List[int]:
 dp = [0] * (n+1)
 offset = 1
 for i in range(1,n+1):
 if offset * 2 == i:
 offset = i
 dp[i] = 1 + dp[i-offset]
 return dp
</code></pre>

#### 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.
<hr>

Example 1: 
Input: n = 2 
Output: [0,1,1] 
Explanation: 
0 --> 0 
1 --> 1 
2 --> 10

Example 2: 
Input: n = 5 
Output: [0,1,1,2,1,2] 
Explanation: 
0 --> 0 
1 --> 1 
2 --> 10 
3 --> 11 
4 --> 100 
5 --> 101 

<hr>


```
class Solution:
 def countBits(self, n: int) -> List[int]:
 dp = [0] * (n+1)
 offset = 1
 for i in range(1,n+1):
 if offset * 2 == i:
 offset = i
 dp[i] = 1 + dp[i-offset]
 return dp
 
```

11. Counting Bits

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.