Python solution linear time complexity O(N), space complexity O(N)


  • 0
    A
    class Solution(object):
        def countBits(self, num):
            """
            :type num: int
            :rtype: List[int]
            """
            if not num: return [0]
            myMap = [0]*(num+1)
            myMap[0], myMap[1] = 0, 1
            power = 1
            while (2**power<=num):
                start = 2**power
                end = 2**(power+1) - 1
                ptr = start
                while(ptr<=end and ptr<=num):
                    myMap[ptr] = myMap[ptr-start]+1
                    ptr+=1
                power += 1
            
            return myMap

Log in to reply
 

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