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 =  if num > 0: amountToAdd = 1 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] """ answer = [0, 1] while len(answer) <= num: answer.extend(map(lambda x:x+1, answer)) return answer[:num+1]
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 =  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 =  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 =  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.