# Python With A Recursive Relationship 288 ms

• You can find the number of ones in the binary representation using the following relationship. If the number is a power of 2, there is only a single one in the binary rep. Otherwise, find the largest power of two smaller than the current number and the difference between the 2-power and our number. We will have already solved the problem for the difference so we can just look it up. For instance, suppose the number is 7 and we have already figured out the solutions for all numbers up to seven (i.e [0,1,1,2,1,2,2]. Therefore, we can consider 7 as the sum of 4 (largest 2-power smaller than 7) and 3 (the difference). Since 4 is a 2-power, we know it takes up a single one, and we already have the solution for 3. 1 + ans[3] = 1 + 2 = 3 ones in the binary representation of 7.

``````    if num == 0:
return [0]
ans = [0 for i in range(num+1)]
prev = 0
cur = 1
for i in range(1,num+1):
if i == cur:
ans[i] = 1
prev = cur
cur = 2*cur
else:
ans[i] = (1 + ans[i-prev])
return ans``````

• Thank you！very smart and clear！

• one according to the most voted question

`````` class Solution(object):
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
res = [0, 1]
if num <= 1:
return res[:num+1]
for i in range(2, num+1):
res.append(res[i>>1] + res[i&1])
return res``````

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