Python O(n) space 1 pass solution with explanations


  • 0
    K

    Let's start with observations:

    • number : number of ones
    • 0 : 0
    • 1 : 1
    • [2,3] : [1,2]
    • [4,5,6,7] : [1,2,2,3]
    • [8:16] : [1,2,2,3,2,3,3,4]
    • [16:32] : [1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5]

    Let curr be one of the above blocks, then the next block is gonna be

    curr + [1+j for j in curr]

    Codes:

    class Solution(object):
        def countBits(self, num):
            if num==0: return [0]
            res, curr, p = [0,1], [1], int(math.log(num, 2))-1
            for i in range(p): 
                curr += [1+j for j in curr]
                res += curr
            return res + curr[:num-len(res)+1] if num-len(res)+1<len(curr) else \
            res + curr + [1+j for j in curr[:num-len(res)-len(curr)+1]]
    

    Inspired by @parikhv, a revised version is given as

    class Solution(object):
        def countBits(self, num):
            if num==0: return[0]
            dp = [0]*(num+1)
            for i in range(1,num+1): dp[i] = dp[i/2] if i%2==0 else dp[i/2]+1
            return dp

Log in to reply
 

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