Python O(log(N)) simple solution


  • 1
    M

    Notice the pattern?
    N

    0
    1 2 3
    4 5 6 7
    8 9 10 11 12 13 14 15 16 17
    

    Number of ones

    0 
    1 
    1 2
    1 2 2 3
    1 2 2 3 2 3 3 4
    1 2 2 3 2 3 3 4 2 3 3 4 3 4 4 5
    
        def countBits(self, num):
            """
            :type num: int
            :rtype: List[int]
            """
            r = []
            t = 2
            prev = [1]
            while t <= (num<<1):
                t = t << 1
                r += prev
                prev = prev + [n+1 for n in prev]
            return [0] + r[0:num]
    

    Assuming list concatenation and sum one to a list is made in parallel, then complexity will be O(log(n))


Log in to reply
 

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