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 <= 109Problem Overview: Given an integer n, count how many numbers in the range [0, n] have no consecutive 1s in their binary representation. The constraint applies to adjacent bits only, so 10101 is valid while 110 is not.
Approach 1: Dynamic Programming with Fibonacci Pattern (O(log n) time, O(1) space)
The key observation: the number of valid binary strings of length k without consecutive 1s follows a Fibonacci-style recurrence. If the current bit is 0, the remaining bits can be any valid sequence of length k-1. If the current bit is 1, the next bit must be 0, leaving k-2 positions. Precompute counts for each bit length using dynamic programming. Then iterate through the bits of n from most significant to least significant. Whenever you encounter a 1, add the count of valid numbers with that prefix but with the current bit flipped to 0. If two consecutive 1s appear in n, stop early because any extension becomes invalid. This technique is a classic example of dynamic programming combined with binary prefix analysis.
Approach 2: Recursive with Memoization (Digit DP) (O(log n) time, O(log n) space)
This method treats the binary representation as a digit DP problem. Traverse the bits recursively while tracking three states: the current index, whether the previous bit was 1, and whether the prefix is still restricted by n. If the previous bit was 1, you cannot place another 1. Memoize results for states where the prefix is already smaller than n. The recursion explores valid combinations while pruning invalid branches early. This pattern appears frequently in dynamic programming and bit manipulation problems that count numbers under a constraint.
Recommended for interviews: The Fibonacci-style dynamic programming approach is what interviewers typically expect. It runs in O(log n) time by scanning the binary digits once and uses constant space. The recursive digit-DP solution demonstrates deeper understanding of counting problems with prefix constraints, but the iterative DP version is shorter and easier to implement under interview pressure.
This approach utilizes dynamic programming to count the number of non-negative integers without consecutive ones. By breaking down the problem, we can avoid redundant work by storing solutions to subproblems.
The C solution utilizes a dynamic programming array dp to store the number of valid integers for each bit length. As we iterate over each bit in n, we decide whether to add the number of valid binary numbers of that length. We keep track of consecutive 1s and adjust our result accordingly. The final result is incremented to account for the number itself if valid.
Time Complexity: O(1) since we iterate over a fixed number of bits (30 bits for int).
Space Complexity: O(1) for storing a constant size dp array.
In this approach, we tackle the problem recursively and use memoization to store and retrieve solutions to subproblems, thereby optimizing overlapping subproblem calculations.
This C++ solution implements depth-first search recursion, coupled with an unordered_map that serves as the memoization strategy. The function performs bitwise checks and combines overlaps using the memo to prevent redundant calculations.
Time Complexity: Generally O(log n), as the recursion iterates over each bit once.
Space Complexity: O(log n) due to the recursive call stack and memo storage.
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:
represents the current position being searched, starting from the highest digit, i.e., the first character of the binary string. represents the digit at the previous binary position. For this problem, the initial value of pre is 0. 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:
and j are 1, it means there are consecutive 1, so we skip it. 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:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(1) since we iterate over a fixed number of bits (30 bits for int). Space Complexity: O(1) for storing a constant size dp array. |
| Recursive with Memoization | Time Complexity: Generally O(log n), as the recursion iterates over each bit once. Space Complexity: O(log n) due to the recursive call stack and memo storage. |
| Digit DP | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming (Fibonacci + Bit Scan) | O(log n) | O(1) | Best for interviews and production. Efficiently counts valid numbers by scanning binary digits. |
| Recursive Digit DP with Memoization | O(log n) | O(log n) | Useful for learning digit DP patterns or adapting to similar counting constraints. |
Non negative Integers without Consecutive Ones | Leetcode 600 | Live coding session • Coding Decoded • 5,106 views views
Watch 9 more video solutions →Practice Non-negative Integers without Consecutive Ones with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor