# Leetcode Counting Bits problem solution

In this Leetcode Counting Bits problem solution we have 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.

## Problem solution in Python.

```class Solution(object):
def countBits(self, num):
if num == 0: return [0]
dp = [0]*(num+1)
dp[0] = 0
dp[1] = 1
for i in range(2, num+1):
if i%2 == 0: dp[i] = dp[i/2]
else: dp[i] = 1 + dp[(i-1)/2]

return dp
```

## Problem solution in Java.

```class Solution {
public int[] countBits(int num) {
int[] dp = new int[num+1];

dp[0] = 0;
int nearest = 0;
for (int k = 1; k <= num; k++) {
if ((k & (k-1)) == 0) {
dp[k] = 1;
nearest = k;
} else {
dp[k] = dp[k-nearest] + dp[nearest];
}
}

return dp;
}
}
```

## Problem solution in C++.

```class Solution {
public:
vector<int> countBits(int num) {
vector<int>res(num+1);
res[0] = 0;
for(int i = 1 ; i <= num ; i++)
res[i] = res[i/2] + (i&1);
return res;
}
};
```

## Problem solution in C.

```int* countBits(int num, int* returnSize) {
int i =0,k = 4, ano = 4;
int num1 = num;
*returnSize = (num+1);
int *arr = malloc(sizeof(int)*(num+1));
if(num1>3)
num1 = 3;
switch(num1){
case 3:
arr[3] = 2;
num--;
num1--;
case 2:
arr[2] = 1;
num--;
num1--;
case 1:
arr[1] = 1;
num--;
num1--;
case 0:
arr[0] = 0;
num--;
break;
}
while(num >= 0){
if(i>=ano) {
ano *= 2;
i = 0;
}
arr[k] = arr[i%ano] + 1;
i++;
k++;
num--;
}
return arr;

}
```