Non-negative Integers without Consecutive Ones

Non-negative Integers without Consecutive Ones

What is this problem about?

The Non-negative Integers without Consecutive Ones problem asks you to count integers from 0 to n (inclusive) whose binary representation contains no two consecutive 1-bits. This hard coding problem uses digit DP on binary numbers, relating the count to Fibonacci-like sequences.

Why is this asked in interviews?

Pocket Gems, Microsoft, and Bloomberg ask this hard problem because it connects binary representation analysis with Fibonacci numbers — a surprising and elegant mathematical insight. The dynamic programming interview pattern is central, and the problem tests whether candidates can think about integers in terms of their bit patterns.

Algorithmic pattern used

Digit DP (or Fibonacci insight). The count of valid k-bit numbers (no consecutive 1s) follows the Fibonacci sequence: f(k) = fib(k+2). For a given n, decompose it bit by bit from the highest to lowest. For each '1' bit at position k, count all valid numbers with the same prefix but a '0' at position k (contributing fib(k+1) numbers). If two consecutive '1' bits appear in n itself, stop counting. The answer is the sum of these Fibonacci contributions.

Example explanation

n = 5 (binary: 101).

• Valid numbers 0-5 with no consecutive 1s: 0 (00), 1 (01), 2 (10), 4 (100), 5 (101). That's 5 numbers. 3 (11) is invalid. Using Fibonacci approach: highest bit at position 2 (value 4). Count: fib(3)+fib(1)+1 (for n=5 itself, which is valid since 101 has no consecutive 1s) = 3+1+1 = 5. ✓

Common mistakes candidates make

• Using brute force O(n) to check each number's binary representation.
• Not recognizing the Fibonacci structure in the valid count.
• Off-by-one in the Fibonacci index.
• Incorrectly handling the case where n itself has consecutive 1-bits.

Interview preparation tip

Bit-counting problems with "no two consecutive 1s" are classic Fibonacci-on-binary problems. The key insight: the count of valid k-bit numbers follows fib(k+2). To count valid numbers ≤ n, decompose n bit by bit, adding Fibonacci contributions at each '1' bit. This digit DP approach works for any constraint on binary patterns. Practice problems involving "count binary strings with property X" — they often reduce to known sequences (Fibonacci, Catalan, etc.).