Non-negative Integers without Consecutive Ones

Hard
1617.

Non-negative Integers without Consecutive Ones

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.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @return {number}
 */
var findIntegers = function(n) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

  1. Hint 1

    Count first for a full range: how many bit strings of length k have no two adjacent ones? Condition on the first bit.

  2. Hint 2

    That count is Fibonacci-like: f(k) = f(k - 1) + f(k - 2) with f(0) = 1, f(1) = 2, and it equals the number of valid integers in [0, 2^k).

  3. Hint 3

    Walk the bits of n from the top. At each 1 bit at position k, every number that has a 0 there and matches n above it is below n: add f(k). Stop as soon as n itself has two adjacent ones; if you never stop, n is 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

  1. Precompute f[0] = 1, f[1] = 2, f[k] = f[k-1] + f[k-2] for k up to 31.
  2. Scan bit positions k from 30 down to 0, remembering whether the previous (higher) bit of n was 1.
  3. When bit k of n is 1: add f[k] (numbers with a 0 here and anything valid below). If the previous bit was also 1, return the total now — every remaining number with this prefix contains 11.
  4. If the scan finishes, n itself 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 n itself (and 0): the final + 1 only applies when n has no adjacent ones.
  • Brute force up to 10^9 is 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 + 1

Java

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