Non-negative Integers without Consecutive Ones: Fibonacci DP on Bits

May 21, 20266 min read

leetcodeproblemharddynamic-programming

Given a positive integer n, count how many integers in the range [0, n] have binary representations that do not contain consecutive ones. This is LeetCode 600: Non-negative Integers without Consecutive Ones, and it is a classic example of digit DP powered by the Fibonacci sequence.

For example, when n = 5, the binary representations of 0 through 5 are 000, 001, 010, 011, 100, 101. The number 3 (011) is the only one with consecutive 1s, so the answer is 5.

Numbers 0 through 5 in binary. Green cells mark valid numbers (no consecutive 1s). Orange cells in 3 (011) show the violation. The Fibonacci table below shows how counts grow: fib[i] = fib[i-1] + fib[i-2].

The approach: Fibonacci meets binary

The brute-force solution would check every number from 0 to n, convert each to binary, and verify that no two adjacent bits are both 1. That takes O(n log n) time and is far too slow when n can be up to 10^9.

The fast approach relies on a beautiful observation: the count of binary strings of length k with no consecutive 1s follows the Fibonacci sequence.

Think about it this way. A binary string of length k with no consecutive 1s can either:

Start with 0, followed by any valid string of length k - 1
Start with 10, followed by any valid string of length k - 2 (because after placing a 1, the next bit must be 0)

That recurrence, count(k) = count(k - 1) + count(k - 2), is exactly the Fibonacci relation. For length 1, there are 2 valid strings (0 and 1). For length 2, there are 3 (00, 01, 10). For length 3, there are 5. The pattern is 1, 2, 3, 5, 8, 13, and so on.

But you do not want to count all binary strings of a given length. You want to count only those that are at most n. So you process the bits of n from the most significant bit (MSB) to the least significant bit (LSB), and at each 1 bit you add the Fibonacci count for the remaining positions. This accounts for all valid numbers where that bit would be 0 instead of 1 (which are guaranteed to be smaller than n).

If you ever encounter two consecutive 1 bits in n, you stop early. Every number that matches n up to that point has already exceeded the valid range. If you make it through all bits without hitting consecutive 1s, add 1 to include n itself.

The Fibonacci connection here is the same constraint as House Robber. When you cannot pick two adjacent items (houses to rob, or bit positions to set to 1), the count of valid configurations grows according to the Fibonacci sequence. Once you see this pattern, you will recognize it in many other problems.

Clean solution

def findIntegers(n):
    bits = bin(n)[2:]
    k = len(bits)

    fib = [0] * (k + 2)
    fib[0] = 1
    fib[1] = 2
    for i in range(2, k + 1):
        fib[i] = fib[i - 1] + fib[i - 2]

    result = 0
    prev_bit = 0

    for i in range(k):
        if bits[i] == '1':
            result += fib[k - i - 1]
            if prev_bit == 1:
                return result
            prev_bit = 1
        else:
            prev_bit = 0

    return result + 1

Line by line walkthrough

bits = bin(n)[2:] converts n to a binary string without the 0b prefix. For n = 5, this gives "101".

k = len(bits) captures the bit length. This tells you how large the Fibonacci table needs to be.

The Fibonacci table uses a shifted definition: fib[0] = 1 (one valid string of length 0, the empty string) and fib[1] = 2 (two valid strings of length 1: "0" and "1"). Each subsequent entry is the sum of the previous two. The value fib[j] counts how many valid binary strings of length j have no consecutive 1s.

result = 0 accumulates the count of valid numbers strictly less than n.

prev_bit = 0 tracks whether the previous bit in n was a 1.

The loop scans bits from MSB to LSB. When you encounter a 1 at position i, you add fib[k - i - 1]. This is the count of all valid completions for the remaining k - i - 1 bit positions, assuming you set the current bit to 0 (making the number strictly smaller than n from this point onward).

After adding the Fibonacci value, you check if prev_bit == 1. If the previous bit was also 1, that means n has consecutive 1s at this point. Any number that matches n up through these two bits would also have consecutive 1s, so you return early.

When the bit is 0, you simply reset prev_bit to 0 and move on.

return result + 1 at the end handles the case where n itself has no consecutive 1s. Since the loop only counted numbers strictly less than n, you add 1 to include n in the count.

Practice bit manipulation DP

Visual walkthrough

Let's trace through the algorithm with n = 5 (binary 101):

Step 1: Convert n to binary, build Fibonacci table

n=5 in binary is "101" with k=3 bits. Build fib[0]=1, fib[1]=2, fib[2]=3. Each value counts how many valid binary strings exist at that length.

Step 2: Scan bit i=0 (MSB), value is '1'

Bit 0 is '1'. Add fib[2]=3 to result. This counts all 3-bit numbers starting with '0' that have no consecutive 1s. Set prev_bit=1.

Step 3: Scan bit i=1, value is '0'

Bit 1 is '0'. No Fibonacci value to add. Reset prev_bit to 0, which means we have no risk of consecutive 1s at this position.

Step 4: Scan bit i=2 (LSB), value is '1'

Bit 2 is '1'. prev_bit was 0, so no consecutive 1s. Add fib[0]=1 to result (now 4). Set prev_bit=1.

Step 5: All bits scanned, return result + 1

We scanned all bits without finding consecutive 1s in n=5 itself, so it counts as valid. Final answer: 4 + 1 = 5. The valid numbers are 0, 1, 2, 4, and 5.

Complexity analysis

Aspect	Value
Time	O(log n), one pass through the bits of n
Space	O(log n), the Fibonacci array has one entry per bit

For n = 10^9, you process about 30 bits instead of iterating through a billion numbers. This is a massive speedup over the O(n log n) brute force.

Drill dynamic programming patterns

The building blocks

This problem combines two fundamental techniques.

Fibonacci counting. Whenever a problem forbids selecting two adjacent items (bits, houses, elements), the number of valid configurations follows the Fibonacci sequence. You saw this same structure in House Robber, where you cannot rob two adjacent houses. Here, you cannot set two adjacent bits to 1. The math is identical.

Digit DP (bit-by-bit upper bound). Instead of counting all valid binary strings of a given length (which would overcount past n), you walk through the actual bits of n from left to right. At each 1 bit, you split: the "set this bit to 0" branch is fully counted using the Fibonacci table, and the "keep this bit as 1" branch continues the scan. This "tight vs. free" partitioning is the core idea of digit DP, and it shows up in many problems that ask you to count numbers with specific properties within a range.

Edge cases

n = 0. The answer is 1. Zero has no consecutive ones in its binary representation. The return result + 1 at the end handles this correctly.

n with consecutive 1s (e.g., n = 3, binary 11). When you scan the second 1 and see that prev_bit is already 1, you return early. For n=3, the answer is 3 (valid numbers: 0, 1, 2).

Power of 2 (e.g., n = 8, binary 1000). Only one 1 bit followed by all zeros. The scan adds fib[3] = 5 at the first bit, then walks through three 0 bits. Result is 5 + 1 = 6.

All 1s in binary (e.g., n = 7, binary 111). The early return triggers at the second bit position. Make sure the Fibonacci values are precomputed for the full bit length before scanning begins.

From understanding to recall

You have just walked through the Fibonacci digit DP technique, and the connection between consecutive-one-free binary strings and Fibonacci numbers probably clicks right now. But a week from now, will you remember the exact indexing? Will you recall why fib[0] = 1 and fib[1] = 2 instead of the standard Fibonacci base cases? Will the early termination logic come back to you under interview pressure?

Spaced repetition is how you turn "I understand this" into "I can write this cold." You revisit the problem at increasing intervals, rebuild the Fibonacci lookup from scratch, and re-derive the bit-scanning logic each time. After a few reps, the pattern is automatic. The Fibonacci digit DP pattern is one of those building blocks that unlocks a whole family of related problems, and drilling it means you will recognize it instantly the next time a digit DP question appears.

Try CodeBricks free

Counting Bits - Another problem where binary structure drives the DP, building bit counts from previously computed values
House Robber - The same "no two adjacent" constraint applied to house values instead of binary digits
Fibonacci Number - The foundation behind the counting logic used in this problem