Non-negative Integers without Consecutive Ones — Solution
Non-negative Integers without Consecutive Ones solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Non-negative Integers without Consecutive Ones is a hard coding problem on dynamic programming, bit manipulation and Digit DP, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Dynamic Programming, Bit Manipulation, Digit DP
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given a positive integer n, count the integers x with 0 <= x <= n whose binary representation does not contain two adjacent 1 bits.
Example 1
Input: n = 5
Output: 5
Explanation: 0, 1, 2 (10), 4 (100) and 5 (101) qualify; 3 (11) does not.
Example 2
Input: n = 1
Output: 2
Explanation: Both 0 and 1 qualify.
Example 3
Input: n = 2
Output: 3
Constraints
1 <= n <= 10^9
Hints for Non-negative Integers without Consecutive Ones
Hint 1
Count first for a full range: how many bit strings of length
khave no two adjacent ones? Condition on the first bit.Hint 2
That count is Fibonacci-like:
f(k) = f(k - 1) + f(k - 2)withf(0) = 1,f(1) = 2, and it equals the number of valid integers in[0, 2^k).Hint 3
Walk the bits of
nfrom the top. At each1bit at positionk, every number that has a0there and matchesnabove it is belown: addf(k). Stop as soon asnitself has two adjacent ones; if you never stop,nis valid — add 1.
How to solve Non-negative Integers without Consecutive Ones
Valid numbers below a power of two are counted by a Fibonacci recurrence. Every number x <= n either equals n or first differs from n at some bit where n has a 1 and x has a 0; below that bit x is free, so each such branch contributes a Fibonacci count — provided the prefix shared with n is itself valid.
Approach
- Precompute
f[0] = 1, f[1] = 2, f[k] = f[k-1] + f[k-2]forkup to 31. - Scan bit positions
kfrom 30 down to 0, remembering whether the previous (higher) bit ofnwas1. - When bit
kofnis1: addf[k](numbers with a0here and anything valid below). If the previous bit was also1, return the total now — every remaining number with this prefix contains11. - If the scan finishes,
nitself is valid: return total + 1.
Why it works
f(k) counts length-k strings with no adjacent ones: a leading 0 leaves f(k-1) options, a leading 1 forces a 0 next and leaves f(k-2). Grouping all x < n by the highest bit where they differ from n gives disjoint groups, each a fixed valid prefix followed by 0 and k free bits; placing a 0 after the prefix can never create 11, so the group has exactly f(k) valid members. Once n's own prefix contains 11, no later group is valid.
Complexity
- Time —
O(log n) - Space —
O(log n) (O(1) with a fixed 32-entry table)
Pitfalls
- Forgetting to count
nitself (and0): the final+ 1only applies whennhas no adjacent ones. - Brute force up to
10^9is far too slow. - Stopping at the second of two adjacent ones — after adding its
f[k]— not before.
Reference solution
Python
def findIntegers(n: int) -> int:
f = [1, 2]
for _ in range(30):
f.append(f[-1] + f[-2])
total = 0
prev = 0
for k in range(30, -1, -1):
if (n >> k) & 1:
total += f[k]
if prev:
return total
prev = 1
else:
prev = 0
return total + 1Java
public static int findIntegers(int n) {
int[] f = new int[32];
f[0] = 1;
f[1] = 2;
for (int i = 2; i < 32; i++) f[i] = f[i - 1] + f[i - 2];
int total = 0;
boolean prev = false;
for (int k = 30; k >= 0; k--) {
if (((n >> k) & 1) == 1) {
total += f[k];
if (prev) return total;
prev = true;
} else {
prev = false;
}
}
return total + 1;
}C++
int findIntegers(int n) {
int f[32];
f[0] = 1;
f[1] = 2;
for (int i = 2; i < 32; i++) f[i] = f[i - 1] + f[i - 2];
int total = 0;
bool prev = false;
for (int k = 30; k >= 0; k--) {
if ((n >> k) & 1) {
total += f[k];
if (prev) return total;
prev = true;
} else {
prev = false;
}
}
return total + 1;
}JavaScript
var findIntegers = function(n) {
var f = [1, 2];
for (var i = 2; i <= 31; i++) f.push(f[i - 1] + f[i - 2]);
var total = 0, prev = 0;
for (var k = 30; k >= 0; k--) {
if ((n >> k) & 1) {
total += f[k];
if (prev) return total;
prev = 1;
} else {
prev = 0;
}
}
return total + 1;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Bit Manipulation