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 <= 109This 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.
C++
Java
Python
C#
JavaScript
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.
Python
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.
| 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. |
I solved too many Leetcode problems • NeetCodeIO • 101,495 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