Python With A Recursive Relationship 288 ms

  • 1

    You can find the number of ones in the binary representation using the following relationship. If the number is a power of 2, there is only a single one in the binary rep. Otherwise, find the largest power of two smaller than the current number and the difference between the 2-power and our number. We will have already solved the problem for the difference so we can just look it up. For instance, suppose the number is 7 and we have already figured out the solutions for all numbers up to seven (i.e [0,1,1,2,1,2,2]. Therefore, we can consider 7 as the sum of 4 (largest 2-power smaller than 7) and 3 (the difference). Since 4 is a 2-power, we know it takes up a single one, and we already have the solution for 3. 1 + ans[3] = 1 + 2 = 3 ones in the binary representation of 7.

        if num == 0:
            return [0]
        ans = [0 for i in range(num+1)]
        prev = 0
        cur = 1
        for i in range(1,num+1):
            if i == cur:
                ans[i] = 1
                prev = cur 
                cur = 2*cur
                ans[i] = (1 + ans[i-prev])
        return ans

  • 0

    Thank you!very smart and clear!

  • 0

    one according to the most voted question

     class Solution(object):
        def countBits(self, num):
            :type num: int
            :rtype: List[int]
            res = [0, 1]
            if num <= 1:
                return res[:num+1]
            for i in range(2, num+1):
                res.append(res[i>>1] + res[i&1])
            return res

Log in to reply

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