Python beats 100% O(n) based on pattern found


  • 2

    [1] 1

    [2-3] 1, 2

    [4-7] 1, 2, 2, 3

    [8-15] 1, 2, 2, 3 | 2, 3, 3, 4

    [16-31] 1, 2, 2, 3 2, 3, 3, 4 | 2, 3, 3, 4 3, 4, 4, 5

    [32-63] 1, 2, 2, 3 2, 3, 3, 4 2, 3, 3, 4 3, 4, 4, 5 | 2, 3, 3, 4 3, 4, 4, 5 3, 4, 4, 5 4, 5, 5, 6

    First half is the same as the previous one, the other half is generated by adding 1 to each in the first half.

    class Solution(object):
        def countBits(self, num):
            """
            :type num: int
            :rtype: List[int]
            """
            ret = [0 for i in xrange(0, num + 1)]
            nextBS = 1
            for i in xrange(1, num + 1):
                if i == nextBS:
                    ret[i] = 1
                    nextBS *= 2
                else:
                    if i < nextBS / 2 + (nextBS) / 4:
                        ret[i] = ret[i - nextBS / 4]
                    else:
                        ret[i] = ret[i - nextBS / 4] + 1
            return ret

Log in to reply
 

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