Given a positive integer n, find the number of non-negative integers less than or equal to n, whose binary representations do NOT contain consecutive ones.

Example 1:

Input: 5
Output: 5
Explanation: 
Here are the non-negative integers 


Note:
1 9

Difficulty: interview

Starter code:

class Solution:
    def findIntegers(self, num: int) -> int:
        

Solutions:
class Solution:
     def findIntegers(self, num):
         """
         :type num: int
         :rtype: int
         """
         dp=[1,2]
         for i in range(2,32):
             dp.append(dp[i-1]+dp[i-2])
         
         bnum=bin(num)[2:]
         size=len(bnum)
         ans=dp[size]
         for i in range(1,size):
             if bnum[i-1]==bnum[i]=='1':
                 #关键 娥娥 对 因为他就是一个二进制数在这儿循环呢
                 #所以他可以这样
                 break
             if bnum[i-1]==bnum[i]=='0':
                 ans-=dp[size-i]-dp[size-i-1]
                 #其实问题就是在于这儿 是在干什么 为什么会有这么一部 算了 先记住
         return ans

class Solution:
     def findIntegers(self, num):
         """
         :type num: int
         :rtype: int
         """
         f = [0 for i in range(32)]
         f[0] = 1
         f[1] = 2
         for i in range(2, 32):
             f[i] = f[i-1] + f[i-2]
         ans = 0
         numL = list(map(int, bin(num)[2:]))
         l = len(numL)
         for i, n in enumerate(numL):
             if n == 1:
                 ans += f[l - i - 1]
                 if i > 0 and numL[i-1] == 1:
                     return ans
         return ans + 1 # include itself since we know if num contains two 1s, it will return before


class Solution:
     def findIntegers(self, num):
         """
         :type num: int
         :rtype: int
         """
         A=bin(num)[2:][::-1]
         
         
         a=[0 for _ in range(len(A))]
         
         b=[0 for _ in range(len(A))]
         
         a[0]=1
         b[0]=1
         
         for i in range(1,len(A)):
             a[i]=a[i-1]+b[i-1]
             b[i]=a[i-1]
         
         n=len(A)
         res=a[n-1]+b[n-1]
         for i in range(n-2,-1,-1):
             if A[i]=='1' and A[i+1]=='1':
                 break
             elif A[i]=='0' and A[i+1]=='0':
                 res-=b[i]
         return res

class Solution:
     def findIntegers(self, num):
         """
         :type num: int
         :rtype: int
         """
         if num<3:
             return num+1
         if num==3:
             return num
         import math
         bits = int(math.log(num,2))
         f = [0]*(bits+1)
         f[0],f[1],f[2] =2,3,4
         for i in range(3,bits+1):
             f[i] = f[i-1]+f[i-2]-1
 
         g = [0]*(bits+1)
         n = num
         b = 0
         res = [0]*(bits+1)
         while n: 
             cur = n%2
             g[b] = cur
             if cur:
                 if not b:
                     res[b] = f[b]
                 elif not res[b-1]:
                     res[b] = f[b]+res[b-1]
                     
                 elif not g[b-1]:
                     res[b] = f[b]+res[b-1]-1
                 else:
                     res[b] = f[b]+f[b-1]-2
                                     
             else:
                 res[b] = res[b-1]
             n = int(n/2)
             b = b+1
         #print(g,f,res)
         return res[-1]


class Solution(object):
     def findIntegers(self, num):
         """
         :type num: int
         :rtype: int
         """
         # A[0] is the lowest bit, A[-1] is the highest bit
         A = bin(num)[2:][::-1]
         # dp[i][0] is the number of integers with (i+1)bits, highest bit is 0 and without consecutive ones
         # dp[i][1] is the number of integers with (i+1)bits, highest bit is 1 and without consecutive ones
         dp = [[1,1] for _ in range(len(A))]
         # res is the number of integers less than A[:i] without consecutive ones.
         res = 1 if A[0] == '0' else 2
         for i in range(1, len(A)):
             dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
             dp[i][1] = dp[i - 1][0]
             # try to get the number of integers less than A[:i+1]
             if A[i - 1: i + 1] == '01':
                 # if A[i-1:i+1]=='01', we can append '1' after integers less than A[:i] without consecutive ones, 
                 # also any integer with (i+1) bits, highest bit is '0', without consecutive ones
                 # is less than A[:i+1]
                 res += dp[i][0]
             elif A[i - 1: i + 1] == '11':
                 # if A[i-1:i+1]=='11', then any integer with i+1 bits and without consecutive ones 
                 # is less than A[:i+1]
                 res = dp[i][0] + dp[i][1]
             # if A[i]=='0', the number of integers  with i+1 bits, less than A[:i+1]  and without 
             # consecutive ones is the same as A[:i]
         return res


class Solution:
     def findIntegers(self, num):
         """
         :type num: int
         :rtype: int
         """
         
         n = bin(num)[2:]        
         mem = [-1] * (len(n) + 1)
         mem[0] = 0
         mem[1] = 0
         def cons(n):
             
             count = 0
             if n == '' or n == '1':
                 return 0
             
             if n[0] == '0':
                 count += cons(n[1:])
             else:
                 if (mem[len(n[1:])] == -1):
                     mem[len(n[1:])] =  cons('1'* len(n[1:]))
                     
                 count += mem[len(n[1:])]
                   
                 if n[1] == '1':
                     count += 1
                     if(n[2:] != ''):
                         count += int(n[2:], 2)
                     count += mem[len(n[2:])]
                 else:
                     count += cons(n[2:])
                 
             return count
         
         
         c = cons(n)    
         
         return num + 1 - c

class Solution:
     def findIntegers(self, num):
         """
         :type num: int
         :rtype: int
         """
         if num<3:
             return num+1
         if num==3:
             return num
         import math
         bits = int(math.log(num,2))
         f = [0]*(bits+1)
         f[0],f[1],f[2] =2,3,4
         for i in range(3,bits+1):
             f[i] = f[i-1]+f[i-2]-1
 
         res = 0
         pre = 0
         flag = False
         for i in range(bits+1):
             if num&(1<<i):
                 
                 if pre:
                     res = f[i]+f[i-1]-2
 
                 elif flag:
                     res = f[i]+res-1
                 else:
                     res = f[i]+res
                     flag = True
             pre = num&(1<<i)
             #print(pre)
         return res


class Solution:
     def findIntegers(self, num):
         """
         :type num: int
         :rtype: int
         """
         def func(num):
             if num<3:
                 return num+1
             t,k=num,-1
             while t:
                 t>>=1
                 k+=1
             if (num>>(k-1))^3==0:
                 return a[k-1]+a[k]
             return a[k]+func(num-(1<<k))
         
         t,k,a=num,-1,[1,2]
         while t:
             t>>=1
             k+=1
         for i in range(1,k):
             a.append(a[-1]+a[-2])
         return func(num)