Simple Python Solution


  • 10
    S

    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:
                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.


  • 4
    S
    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.


  • 0
    A

    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.


  • 8
    P

    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]
    

  • 0
    W

    '''
    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!!


  • 0
    B

    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
    

Log in to reply
 

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