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


  • 0

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

Log in to reply
 

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