Non-negative Integers without Consecutive Ones: A Fibonacci DP Approach

May 20, 20265 min read

leetcodeproblemharddynamic-programming

Given a positive integer n, you need to 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.

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].

Why this problem matters

This problem sits at the intersection of two patterns you will see again and again: bit manipulation and dynamic programming. On its own, brute-forcing every number up to n and checking for consecutive binary ones would take O(n log n) time, which is way too slow when n can be up to 10^9. The Fibonacci-based digit DP approach solves it in O(log n) time by exploiting a beautiful mathematical relationship between consecutive-one-free binary strings and Fibonacci numbers.

If you have worked through Fibonacci Number or House Robber, you already have the building blocks. This problem shows you how Fibonacci counting extends beyond simple sequences into the domain of digit DP, where you process a number bit by bit instead of iterating through the entire range.

The approach

The key insight is this: the count of binary strings of length k that have no consecutive 1s follows the Fibonacci sequence. For length 1, there are 2 valid strings (0, 1). For length 2, there are 3 (00, 01, 10). For length 3, there are 5. Each length adds the counts from the two previous lengths, exactly like Fibonacci.

To count valid numbers from 0 to n:

Convert n to its binary representation
Build a Fibonacci lookup table up to the bit length of n
Scan the bits of n from the most significant bit (MSB) to the least significant bit (LSB)
Whenever you encounter a 1 bit, add the Fibonacci count for the remaining positions (this accounts for all valid numbers where this bit would be 0 instead)
If you ever see two consecutive 1 bits, stop early - every number from that point onward would exceed n only through invalid territory
If you make it through all bits without hitting consecutive 1s, add 1 to include n itself

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

The Fibonacci array here is slightly different from the standard Fibonacci sequence. fib[0] = 1 and fib[1] = 2 because we are counting the number of valid binary strings of a given length: 1-bit strings have 2 valid options (0 and 1), and 0-bit strings have 1 valid option (the empty string, representing zero). This shifted indexing is what makes the lookup work when you add fib[k - i - 1] at each 1 bit.

Practice this problem with spaced repetition

Step-by-step 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

This is a massive improvement over the naive O(n log n) brute force. For n = 10^9, you are processing about 30 bits instead of a billion numbers.

Build your pattern library with CodeBricks

Edge cases to watch for

n = 0: the answer is 1, since 0 itself has no consecutive ones in its (empty) binary representation. The return result + 1 at the end handles this.
n = 1: the answer is 2, covering both 0 and 1.
n = 3 (binary 11): when you scan the second 1 and see that prev_bit is already 1, you return early. The answer is 3 (valid numbers: 0, 1, 2).
All 1s in binary (e.g., n = 7, binary 111): the early return triggers at the second bit. You need to make sure the Fibonacci values are precomputed for the full bit length before scanning.
Power of 2 (e.g., n = 8, binary 1000): only one 1 bit, no risk of consecutive ones. The scan adds fib[3] = 5 at bit 0, then walks through three 0 bits. Result is 5 + 1 = 6.

The building blocks

This problem combines two fundamental building blocks: Fibonacci counting and digit DP.

The Fibonacci connection is not a coincidence. When you think about placing bits left to right and requiring no two adjacent 1s, you face the same constraint as the House Robber problem. At each position, if you place a 1, the next position must be 0. If you place a 0, the next position is unconstrained. That branching structure produces Fibonacci growth.

The digit DP part is about handling the upper bound n. Instead of counting all valid strings of a given length (which would overcount), you walk through the actual bits of n and carefully partition the count into numbers that are definitely smaller than n (where a 1 bit becomes 0) and numbers that match n up to the current position. This "tight vs. free" technique appears in many digit DP problems.

The structure:

State: current bit position and whether the previous bit was 1
Transition: at a 1 bit, split into "take this bit as 0" (add the Fibonacci count for remaining positions) and "keep this bit as 1" (continue scanning)
Early termination: if two consecutive bits are both 1, all remaining numbers in the "keep" branch are invalid, so stop

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 fib[0] = 0, fib[1] = 1? 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, and re-derive the bit-scanning logic each time. After a few reps, the pattern is second nature.

The Fibonacci digit DP pattern is one of those building blocks that unlocks a family of related problems. Drilling it with spaced repetition means you will recognize it instantly the next time a digit DP problem shows up.

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 in this problem

Try CodeBricks free