# Simple Python Solution

• Code works by constantly extending a list with itself but with the values incremented by 1.

``````def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""

iniArr = [0]
if num > 0:
while len(iniArr) < num + 1:
iniArr.extend([x+1 for x in iniArr])

return iniArr[0:num+1]
``````

Simple python solution that runs in O(n) time. Let me know if there are any ways to improve it.

• ``````def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""

``````

A four liner that does the same thing as above. The above had a few redundancies.

• Your code is based the grouping strategy, but exists some unnecessary compution, e.g. num = 17, 33, etc. Relatively speaking, I think the DP solution is more efficiency and easier to understand and implement.

• No improvements, just try to make it easier to understand with less function:

``````class Solution(object):
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
res = [0]
while len(res) <= num:
res += [i+1 for i in res]
return res[:num+1]
``````

• '''
return [bin(each).count('1') for each in list(range(num+1))]
'''
I think the run time of this solution is aiso O(n),but it is accepted!!

• A couple more ways, the only difference between them is how to handle getting the index to add 1 from.

``````def countBits(self, num):
ones = [0]
power_of_two, j = 2, 0
for i in xrange(1,num+1):
ones.append(ones[j]+1)
j += 1
if i+1 == power_of_two:
j = 0
power_of_two *= 2

return ones

def countBits1(self, num):
ones = [0]
for i in xrange(1,num+1):
# bitwise trick from @fengcc 's solution
ones.append(ones[i&(i-1)]+1)

return ones
``````

• @startingwars How is this O(n)? You have that list comprehension in the loop, shouldn't it be O(n*(n+1)/2) about O(n^2)?

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