## Algorithm

Problem Name: 338. 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`.

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
```

Constraints:

• `0 <= n <= 105`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
int* countBits(int num, int* returnSize) {
int *p, i;

p = malloc((num + 1) * sizeof(int));
//assert(p);
*returnSize = num + 1;

p[0] = 0;
for (i = 1; i  < = num; i ++) {
p[i] = p[i & (i - 1)] + 1;  // i & (i - 1) is to remove a bit from tail
}

return p;
}
``````
Copy The Code &

Input

cmd
n = 2

Output

cmd
[0,1,1]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int[] countBits(int n) {
int[] numofOnes = new int[n + 1];
for (int i = 1; i  < = n; i++) {
numofOnes[i] = numofOnes[i / 2] + i % 2;
}
return numofOnes;
}
}
``````
Copy The Code &

Input

cmd
n = 2

Output

cmd
[0,1,1]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const countBits = function (num) {
const f = new Array(num + 1).fill(0)
for (let i = 1; i  < = num; i++) f[i] = f[i >> 1] + (i & 1)
return f
}
``````
Copy The Code &

Input

cmd
n = 5

Output

cmd
[0,1,1,2,1,2]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def countBits(self, num: int) -> List[int]:
return [bin(i)[2:].count('1') for i in range(num + 1)]
``````
Copy The Code &

Input

cmd
n = 5

Output

cmd
[0,1,1,2,1,2]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
namespace LeetCode
{
public class _0338_CountingBits
{
public int[] CountBits(int num)
{
var result = new int[num + 1];
int b = 1;
while (b  < = num)
{
var i = 0;
while (i < b && b + i <= num)
{
result[i + b] = result[i] + 1;
i++;
}

b <<= 1;
}

return result;
}
}
}
``````
Copy The Code &

Input

cmd
n = 2

Output

cmd
[0,1,1]