# A DP solution in C

• DP equation:

• arr[i] == i&1? arr[i/2]+1 : arr[i/2];

``````//AC - 40ms;
int* countBits(int num, int *returnSize)
{
num++;
*returnSize = num;
int* arr = (int*)malloc(sizeof(int)*num);
arr[0] = 0;
for(int i = 1; i < num; i++)
arr[i] = (i&1)? arr[i>>1]+1 : arr[i>>1];
return arr;
}``````

• it's faster;

``````int* countBits(int num, int *returnSize)
{
num++;
*returnSize = num;
int* arr = (int*)malloc(sizeof(int)*num);
arr[0]=0;
//memset(arr, 0, sizeof(int)*num);
for(int i = 1; i < num; i++)
arr[i] = (i&1)? arr[i>>1]+1 : arr[i>>1];
return arr;
``````

• Indeed, it's needless to set all elements, and only initializing the first actually saves some time from 44ms to 40ms. Thanks for your feedback!

• It's a beautiful solution.
Thank you a lot :)

• @LHearen
it's very clever.
Thanks a lot!

• Very nice, I don't know if it would help, but you might consider the following:

``arr[i] = arr[i>>1] + (i&1);``

• @sganje This can do but to some extent, it loses some readability. Good idea.

• @LHearen said in A DP solution in C:

arr[i] == i&1? arr[i/2]+1 : arr[i/2];

Awesome as usual.

• @Salkexy2 C++ solution is also enclosed now.

``````class Solution {
public:
vector<int> countBits(int num) {
vector<int> v(1,0);
for(int i = 1; i <= num; ++i)
v.push_back(v[i>>1]+(i&1));
return v;
}
};
``````

• It is a clover answer, thank you!

• And this is the python answer.

``````# Runtime: 224 ms
class Solution(object):
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
result = [0]
for i in range(1, num + 1):
result.append(result[i>>1] + 1 if i&1 else result[i>>1])
return result
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.