# Python: No bitwise yet 99.43 percentile speed

• 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:
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
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

Code:

``````class Solution(object):
def countBits(self, num):
"""
:type num: int
:rtype: List[int]
"""
L=[0,1,1,2,1,2,2,3]

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?

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

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

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