A fast Python solution (beat 95%+) with explanation


  • 0
    A
    class Solution(object):
        def countBits(self, num):
            """
            :type num: int
            :rtype: List[int]
            """
            # Catch the edge case when num = 0
            if num == 0: return [0]
            import math, copy
            mem = [0]
            # calculate the power so that num < 2 ** (power+1)
            power = int(math.log(num,2))
            # we can easily grow the table by math, 
            # e.g. # of ones for 2**power + c = # of ones for c + 1
            for p in range(power+1): mem = mem + [e+1 for e in mem]
            return mem[:num+1]
    

Log in to reply
 

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