Non-negative Integers without Consecutive Ones solution and explanation
Google
9 more videos on this problem
Non negative Integers without Consecutive Ones | Leetcode 600 | Live coding sessionCoding Decoded · 15:26 · 5K views
Non-negative Integers without Consecutive Ones | Live Coding with Explanation | Leetcode - 600Algorithms Made Easy · 17:29 · 4K views
L-04. Digit DP | Non-negative Integers without Consecutive Ones | Leetcode 600 | Intuition + CodeWhy Not DP [By Piyush Raj] · 24:41 · 2K views
Non-negative Integers without Consecutive Ones | LeetCode 600 | #FAANGcode Tree · 12:06 · 1K views
LeetCode 600. Non-negative Integers without Consecutive OnesHappy Coding · 30:47 · 1K views
LeetCode Live: 600 Non-negative Integers without Consecutive Ones, 04/24/2019Huifeng Guan · 51:27 · 1K views
Non-negative Integers without Consecutive Ones | Official Solution Simply ExplainedTanishq Chaudhary · 14:55 · 1K views
Daily Leetcode #481: Jul 25, 2021 - 600. Non-negative Integers without Consecutive OnesProgramming Live with Larry · 20:25 · 809 views
600. Non-negative Integers without Consecutive Ones - LEETCODECode Crusaders · 3:32 · 145 views
Leetcode 0600. Non-negative Integers without Consecutive OnesFearless Learner · 18:28 · 144 views
The problem
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.
class Solution:
def findIntegers(self, num: int) -> int:
dp = [0] * 31
dp[0] = 1
dp[1] = 2
for i in range(2, 31):
dp[i] = dp[i - 1] + dp[i - 2]
prev_bit = 0
result = 0
for i in range(29, -1, -1):
if (num & (1 << i)) != 0:
result += dp[i]
if prev_bit == 1:
return result
prev_bit = 1
else:
prev_bit = 0
return result + 1
if __name__ == "__main__":
sol = Solution()
n = 5
print(sol.findIntegers(n))class Solution {
public int findIntegers(int num) {
int[] dp = new int[31];
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < 31; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int prev_bit = 0, result = 0;
for (int i = 29; i >= 0; i--) {
if ((num & (1 << i)) != 0) {
result += dp[i];
if (prev_bit == 1) {
return result;
}
prev_bit = 1;
} else {
prev_bit = 0;
}
}
return result + 1;
}
public static void main(String[] args) {
Solution sol = new Solution();
int n = 5;
System.out.println(sol.findIntegers(n));
}
}#include <vector>
#include <iostream>
using namespace std;
class Solution {
public:
int findIntegers(int num) {
vector<int> dp(31);
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < 31; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int prev_bit = 0, result = 0;
for (int i = 29; i >= 0; --i) {
if ((num & (1 << i)) != 0) {
result += dp[i];
if (prev_bit == 1) {
return result;
}
prev_bit = 1;
} else {
prev_bit = 0;
}
}
return result + 1;
}
};
int main() {
Solution sol;
int n = 5;
cout << sol.findIntegers(n) << endl;
return 0;
}function findIntegers(num) {
let dp = Array(31).fill(0);
dp[0] = 1;
dp[1] = 2;
for (let i = 2; i < 31; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
let prev_bit = 0, result = 0;
for (let i = 29; i >= 0; i--) {
if ((num & (1 << i)) !== 0) {
result += dp[i];
if (prev_bit === 1) {
return result;
}
prev_bit = 1;
} else {
prev_bit = 0;
}
}
return result + 1;
}
const n = 5;
console.log(findIntegers(n));#include <stdio.h>
#include <string.h>
int findIntegers(int num) {
int dp[31] = {1, 2};
for(int i = 2; i < 31; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
int prev_bit = 0, result = 0;
for (int i = 29; i >= 0; i--) {
if ((num & (1 << i)) != 0) {
result += dp[i];
if (prev_bit == 1) {
return result;
}
prev_bit = 1;
} else {
prev_bit = 0;
}
}
return result + 1;
}
int main() {
int n = 5;
printf("%d\n", findIntegers(n));
return 0;
}using System;
public class Solution {
public int FindIntegers(int num) {
int[] dp = new int[31];
dp[0] = 1;
dp[1] = 2;
for (int i = 2; i < 31; i++) dp[i] = dp[i - 1] + dp[i - 2];
int prev_bit = 0, result = 0;
for (int i = 29; i >= 0; i--) {
if ((num & (1 << i)) != 0) {
result += dp[i];
if (prev_bit == 1) return result;
prev_bit = 1;
} else {
prev_bit = 0;
}
}
return result + 1;
}
public static void Main(string[] args) {
Solution sol = new Solution();
int n = 5;
Console.WriteLine(sol.FindIntegers(n));
}
}In Python, the solution similarly utilizes a dp list to manage the counts of valid integer representations without consecutive ones for binary integers up to 31-bit. This implementation iterates over each bit of num to calcualte the total valid integers.
Time Complexity: O(1) due to constant binary digit evaluation.
Space Complexity: O(1) owing to a fixed-size dp list.
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.
class Solution:
def __init__(self):
self.memo = {}
def dfs(self, pos, is_tight, prev_one, bits):
if pos == -1:
return 1
if not is_tight and (pos, prev_one) in self.memo:
return self.memo[(pos, prev_one)]
limit = bits[pos] if is_tight else 1
res = 0
for i in range(limit + 1):
if prev_one and i == 1:
continue
res += self.dfs(pos - 1, is_tight and i == bits[pos], i == 1, bits)
if not is_tight:
self.memo[(pos, prev_one)] = res
return res
def findIntegers(self, num: int) -> int:
bits = []
while num:
bits.append(num & 1)
num >>= 1
return self.dfs(len(bits) - 1, True, False, bits)
if __name__ == "__main__":
sol = Solution()
n = 5
print(sol.findIntegers(n))#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
class Solution {
private:
unordered_map<int, int> memo;
int dfs(int pos, bool is_tight, bool prev_one, vector<int>& bits) {
if (pos == -1) return 1;
if (!is_tight && memo.count(pos * 2 + prev_one)) return memo[pos * 2 + prev_one];
int limit = is_tight ? bits[pos] : 1;
int res = 0;
for (int i = 0; i <= limit; ++i) {
if (prev_one && i == 1) continue;
res += dfs(pos - 1, is_tight && i == bits[pos], i == 1, bits);
}
if (!is_tight) memo[pos * 2 + prev_one] = res;
return res;
}
public:
int findIntegers(int num) {
vector<int> bits;
while (num) {
bits.push_back(num & 1);
num >>= 1;
}
return dfs(bits.size() - 1, true, false, bits);
}
};
int main() {
Solution sol;
int n = 5;
cout << sol.findIntegers(n) << endl;
return 0;
}The Python solution mirrors the C++ solution by breaking down the integer into binary bits and evaluating recursively through depth-first search. It stores computed results in a dictionary to avoid re-calculating overlapping subproblems.
Time Complexity: Typically O(log n), limited by the recursive depth equivalent to the number of bits.
Space Complexity: O(log n) for the recursion depth and memo dictionary.
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 ofpreis0. - 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
andjare1, it means there are consecutive1, so we skip it. - Otherwise, we recurse to the next level, update pre
toj, and updatelimitto the logical AND oflimitand whetherjequalsup.
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:
function findIntegers(n: number): number {
const m = n.toString(2).length;
const f: number[][] = Array.from({ length: m }, () => Array(2).fill(-1));
const dfs = (i: number, pre: number, limit: boolean): number => {
if (i < 0) {
return 1;
}
if (!limit && f[i][pre] !== -1) {
return f[i][pre];
}
const up = limit ? (n >> i) & 1 : 1;
let ans = 0;
for (let j = 0; j <= up; ++j) {
if (pre === 1 && j === 1) {
continue;
}
ans += dfs(i - 1, j, limit && j === up);
}
if (!limit) {
f[i][pre] = ans;
}
return ans;
};
return dfs(m - 1, 0, true);
}func findIntegers(n int) int {
m := bits.Len(uint(n))
f := make([][2]int, m)
for i := range f {
f[i] = [2]int{-1, -1}
}
var dfs func(i, pre int, limit bool) int
dfs = func(i, pre int, limit bool) int {
if i < 0 {
return 1
}
if !limit && f[i][pre] != -1 {
return f[i][pre]
}
up := 1
if limit {
up = n >> i & 1
}
ans := 0
for j := 0; j <= up; j++ {
if j == 1 && pre == 1 {
continue
}
ans += dfs(i-1, j, limit && j == up)
}
if !limit {
f[i][pre] = ans
}
return ans
}
return dfs(m-1, 0, true)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(1) due to constant binary digit evaluation. Space Complexity: O(1) owing to a fixed-size dp list. |
| Recursive with Memoization | Time Complexity: Typically O(log n), limited by the recursive depth equivalent to the number of bits. Space Complexity: O(log n) for the recursion depth and memo dictionary. |
| Digit DP | – |
Complexity analysis
| 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. |
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.