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

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

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

Solutions:
class Solution:

	def findIntegers(self, num):
		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):
		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


class Solution:

	def findIntegers(self, num):
		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):
		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
		return res[-1]


class Solution(object):

	def findIntegers(self, num):
		A = bin(num)[2:][::-1]
		dp = [[1, 1] for _ in range(len(A))]
		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]
			if A[i - 1:i + 1] == '01':
				res += dp[i][0]
			elif A[i - 1:i + 1] == '11':
				res = dp[i][0] + dp[i][1]
		return res


class Solution:

	def findIntegers(self, num):
		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):
		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
		return res


class Solution:

	def findIntegers(self, num):

		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)