Description
Given a positive integer n, return the number of the integers in the range [0, n] whose binary representations do not contain consecutive ones.
Example 1:
Input: n = 5 Output: 5 Explanation: Here are the non-negative integers <= 5 with their corresponding binary representations: 0 : 0 1 : 1 2 : 10 3 : 11 4 : 100 5 : 101 Among them, only integer 3 disobeys the rule (two consecutive ones) and the other 5 satisfy the rule.
Example 2:
Input: n = 1 Output: 2
Example 3:
Input: n = 2 Output: 3
Constraints:
1 <= n <= 109
Solution
Python3
class Solution:
def findIntegers(self, n: int) -> int:
n = int(bin(n)[2:])
digits = []
while n > 0:
digits.append(n % 10)
n //= 10
digits.reverse()
N = len(digits)
@cache
def dp(pos, tight, last):
if pos == N:
return 1
res = 0
limit = digits[pos] if tight else 1
for digit in range(0, limit + 1):
if digit == last == 1: continue
res += dp(pos + 1, tight and digit == digits[pos], digit)
return res
return dp(0, True, 0)