Python: No bitwise yet 99.43 percentile speed

  • 1

    This problem creates a very interesting pattern. Some values are used again and then incremented by 1 and then those values are used again.

    For example:
    for num = 3: [0,1,1,2]
    for num = 7: [0,1,1,2,1,2,2,3]
    soon you would see the pattern becoming something like this:
    1,2,2,3, 2,3,3,4,
    1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5
    1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5, 2,3,3,4........

    Understanding the pattern:
    1,2,2,3, <- Assume this to be a list X
    1,2,2,3, 2,3,3,4, <- Then this is a list with X, X1 [where X1 is just X where each element is incremented by 1] Now Label this whole List as Y i.e. Y=[X,X1]
    1,2,2,3, 2,3,3,4, 2,3,3,4, 3,4,4,5 <- Now the same Pattern repeats, as this list is Y, Y1


    class Solution(object):
        def countBits(self, num):
            :type num: int
            :rtype: List[int]
            s = [1,2,2,3]
            while num >= len(L):
                s = s + [i+1 for i in s]
                L  += s
            return L[:num+1]

    This is very similar to other solutions which suggest to extend the list by repeating itself where each element is incremented. This solution takes a lot of time as there are a lot of redundant steps which can be eliminated by understanding the pattern.

    I am not sure what is the time complexity but should be always less than O(N)
    Can someone help me deduce the Time complexity?

  • 0

    I believe you had used DP when you wrote [i+1 for i in s].

  • 0

    @louis925 That is true. Let me fix the title. Thanks!

Log in to reply

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