First if we say f(n)= all integers <=2^n-1 that do not have 2 consecutive ones, then f(n)=f(n-1)+f(n-2). To see this for n=5, f(n)=|0xxxx|+|10xxx| where any sequence xxxx and xxx satisfying non-consecutive ones will do. f(0)=1,f(1)=2,f(2)=3...,Fibonacci sequence.
Let's assume there exists a '11' sequence in A and let A[N1:N1+1] be the first such occurrence. We look at all prefixes P of length n where P[:n]=A[:n] and P[:n+1]<A[:n+1] implies A[n]=1,P[n]=0. For such prefix P any length N-n bit seq. with non-consecutive ones fits our bill.
Ex., Say A=10010001100, N=11, N1=7. Valid prefixes and # such seqs:
Similarly if we have a '11' and a few 1's beyond that we ignore them. Say A=1001100100,N=10,N1=3 then we consider the 1's only until the first 11, since a prefix containing 11 is not valid.
10011000xx=less than A but Not valid
If no such '11' sequence is in num then ans+=1 for counting the num itself. Say A=100101001,N=9,N1=0,
def findIntegers(self, num): """ :type num: int :rtype: int """ N=max(j for j in range(32) if num&(1<<j))+1 fib=[1,2] for j in range(2,N+1): fib.append(fib[j-1]+fib[j-2]) Nlst=[j for j in range(N) if num&(1<<j) and num&(1<<(j+1))] op,N1=(1,0) if len(Nlst)==0 else (0,max(Nlst)) return op+sum(fib[i] for i in range(N1,N+1) if num&(1<<i) )