Python, Non-DP based on Fibonacci seq. O(log2(N)) .

• 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:
100100010xx=f(2)
10010000xxx=f(3)
1000xxxxxx=f(7)
0xxxxxxxxx=f(10)
ans=sum(f[2,3,7,10])

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
10010xxxxx=f(5)
1000xxxxx=f(6)
0xxxxxxxx=f(9)
ans=sum(f[5,6,10])

If no such '11' sequence is in num then ans+=1 for counting the num itself. Say A=100101001,N=9,N1=0,
100101000=f(0)
100100xxx=f(3)
1000xxxxx=f(5)
0xxxxxxxx=f(8)
ans=1+sum(f([0,3,5,8])

``````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) )
``````

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