Watch 10 video solutions for Non-negative Integers without Consecutive Ones, a hard level problem involving Dynamic Programming. This walkthrough by Coding Decoded has 5,106 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |