Skip to main content
Talentd

Non-negative Integers without Consecutive Ones - Solution & Explanation

HardDynamic Programming21 min readAsked at: Amazon, Microsoft, Google +2
Practice this problem

Problem Statement

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

Approach Overview

Problem 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 1: Dynamic Programming Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Recursive with Memoization

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.

Code

C++Python

C++

Python

Complexity

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.

Try this approach in the editor →

Approach 3: 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:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 MemoizationO(log n)O(log n)Useful for learning digit DP patterns or adapting to similar counting constraints.

Video Solution

Non negative Integers without Consecutive Ones | Leetcode 600 | Live coding session • Coding Decoded • 5,210 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Non-negative Integers without Consecutive Ones easy or hard?
LeetCode classifies this problem as Hard because it requires recognizing the Fibonacci relationship between valid binary strings and applying a digit DP style scan of n. Once the pattern is understood, the implementation is relatively short but the insight is non-trivial.
Non-negative Integers without Consecutive Ones Python/Java solution
Python and Java implementations typically precompute a DP array for valid binary sequences, then iterate through the bits of n from the most significant bit. When a 1 is encountered, the algorithm adds the number of sequences that start with 0 at that position. Both implementations run in O(log n) time and use constant extra space.
How to solve Non-negative Integers without Consecutive Ones in O(n)?
The problem is typically solved in O(log n) time rather than O(n) because the algorithm operates on the binary digits of n. Build a DP array where dp[i] stores the number of valid binary strings of length i without consecutive ones. Then iterate through the bits of n, accumulating counts whenever a 1 appears while ensuring no consecutive 1s occur.
What is the best approach for Non-negative Integers without Consecutive Ones?
The optimal approach uses dynamic programming based on a Fibonacci-like recurrence. Precompute how many valid binary strings exist for each bit length, then scan the bits of n from most significant to least significant. Each time you encounter a 1, add the count of numbers formed by placing 0 at that position and filling the remaining bits with valid sequences. The algorithm runs in O(log n) time and O(1) space.
Is Non-negative Integers without Consecutive Ones asked at Google/Amazon/Meta?
This problem represents a common interview pattern involving digit DP and binary constraints. Variants appear in interviews at large tech companies such as Google, Amazon, and Meta where candidates must count numbers under specific digit restrictions. It tests dynamic programming, bit manipulation, and reasoning about binary representations.
What data structure is used in Non-negative Integers without Consecutive Ones?
The main structure is a small dynamic programming array that stores Fibonacci-like counts for binary lengths. The algorithm also uses bit operations to inspect each bit of n. In recursive solutions, a memoization map or DP table caches states defined by index, previous bit, and tight prefix constraint.
What is the time complexity of Non-negative Integers without Consecutive Ones?
The optimal solution runs in O(log n) time because it processes each bit of the binary representation of n once. Precomputing the Fibonacci-style DP array also takes O(log n). Space complexity can be O(1) when using a fixed-size array for bit lengths.

Ready to solve this problem?

Practice Non-negative Integers without Consecutive Ones with our built-in code editor and test cases.

Practice on FleetCode
Previous

Generate Binary Strings Without Adjacent Zeros

Next

House Robber