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
Solutions
Solution 1: Digit DP
This problem essentially asks for the number of numbers in the given range [l, ..r] whose binary representation does not contain consecutive 1s. The count is related to the number of digits and the value of each binary digit. We can use the concept of Digit DP to solve this problem. In Digit DP, the size of the number has little impact on the complexity.
For the range [l, ..r] problem, we generally convert it to the problem of [0, ..r] and then subtract the result of [0, ..l - 1], i.e.:
$$ ans = \sum_{i=0}^{r} ans_i - \sum_{i=0}^{l-1} ans_i $$
However, for this problem, we only need to find the value for the range [0, ..r].
Here, we use memoized search to implement Digit DP. The basic steps are as follows:
First, we get the binary length of the number n, denoted as m. Then, based on the problem information, we design a function dfs(i, pre, limit), where:
- The digit i represents the current position being searched, starting from the highest digit, i.e., the first character of the binary string.
- The digit pre represents the digit at the previous binary position. For this problem, the initial value of pre is 0.
- The boolean limit indicates whether the digits that can be filled are restricted. If there is no restriction, then we can choose [0,1]. Otherwise, we can only choose [0, up].
The function executes as follows:
If i exceeds the length of the number n, i.e., i < 0, it means the search is over, directly return 1. Otherwise, we enumerate the digits j from 0 to up for the position i. For each j:
- If both pre and j are 1, it means there are consecutive 1, so we skip it.
- Otherwise, we recurse to the next level, update pre to j, and update limit to the logical AND of limit and whether j equals up.
Finally, we sum all the results from the recursive calls to the next level, which is the answer.
The time complexity is O(log n), and the space complexity is O(log n). Here, n is the given positive integer.
Similar problems:
- 233. Number of Digit One
- 357. Count Numbers with Unique Digits
- 788. Rotated Digits
- 902. Numbers At Most N Given Digit Set
- 1012. Numbers With Repeated Digits
- 2376. Count Special Integers
class Solution: def findIntegers(self, n: int) -> int: @cache def dfs(i: int, pre: int, limit: bool) -> int: if i < 0: return 1 up = (n >> i & 1) if limit else 1 ans = 0 for j in range(up + 1): if pre and j: continue ans += dfs(i - 1, j, limit and j == up) return ans return dfs(n.bit_length() - 1, 0, True)(code-box)
