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 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, 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] """ 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?
@louis925 That is true. Let me fix the title. Thanks!