Skip to content

600. Non-negative Integers without Consecutive Ones

Difficulty Topics

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

non-negative-integers-without-consecutive-ones.py
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)