LeetCode 600: Non-negative Integers without Consecutive Ones

Problem Restatement

We are given a positive integer n.

We need to count how many integers in the range [0, n] have binary representations that do not contain consecutive 1 bits.

For example, 3 has binary representation:

11

so it is invalid.

But 5 has binary representation:

101

so it is valid.

Return the count of valid integers from 0 through n, inclusive. The official problem asks for integers in [0, n] whose binary representations do not contain consecutive ones.

Input and Output

Example function shape:

def findIntegers(n: int) -> int:
    ...

Examples

Example 1:

n = 5

Output:

5

The integers from 0 to 5 are:

So the answer is 5.

Example 2:

n = 1

Output:

2

Both 0 and 1 are valid.

Example 3:

n = 2

Output:

3

The valid numbers are 0, 1, and 2.

Their binary forms are:

0
1
10

First Thought: Check Every Number

A direct solution is to loop over every number from 0 to n.

For each number:

1. Convert it to binary.
2. Check whether the string contains "11".
3. Count it if it does not.

class Solution:
    def findIntegers(self, n: int) -> int:
        answer = 0

        for x in range(n + 1):
            if "11" not in bin(x):
                answer += 1

        return answer

This is simple, but it is too slow when n is large.

We need to count valid binary strings without enumerating every integer.

Key Insight

The problem is about binary digits, not decimal values.

We can count valid binary strings by length.

Let:

dp[length]

be the number of binary strings of length length that do not contain consecutive ones.

For length 1, the valid strings are:

0
1

For length 2, the valid strings are:

00
01
10

The recurrence is Fibonacci-like:

dp[i] = dp[i - 1] + dp[i - 2]

Why?

A valid string of length i either:

1. Starts with 0, followed by any valid string of length i - 1.
2. Starts with 10, followed by any valid string of length i - 2.

It cannot start with 11.

So we can precompute how many valid suffixes exist for each remaining length.

Then we scan the bits of n from most significant to least significant.

Whenever we see a 1, we can count all valid numbers that put 0 at this bit and then freely fill the remaining lower bits.

Binary Counting Idea

Suppose:

n = 5

Binary:

101

Scan from left to right.

At the first bit, n has 1.

Numbers less than n can put 0 here:

0??

The remaining two bits can be any valid binary string of length 2.

There are 3 such strings:

00
01
10

So we add 3.

Then we follow the original bit 1.

At the next bit, n has 0, so we cannot choose a smaller bit there. Continue.

At the final bit, n has 1.

Numbers can put 0 there:

100

So we add 1.

Finally, n = 101 itself is valid, so we add 1.

Total:

3 + 1 + 1 = 5

Algorithm

1. Convert n to a binary string.
2. Precompute dp, where dp[i] is the number of valid binary strings of length i.
3. Scan the binary string from left to right.
4. Track the previous bit.
5. When the current bit is 1:
   • Add dp[remaining_length], because we can place 0 here and freely fill the rest.
6. If we ever see two consecutive 1s:
   • Stop and return the count so far.
   • We do not add n itself because n is invalid.
7. If the scan finishes without consecutive ones:
   • Add 1 for n itself.
8. Return the count.

Correctness

The DP array counts valid binary suffixes by length. For any length i, every valid string either begins with 0 followed by a valid string of length i - 1, or begins with 10 followed by a valid string of length i - 2. These two cases are disjoint and complete, so the recurrence counts exactly all valid strings of that length.

During the scan of n, when the current bit is 1, choosing 0 at that position creates a number strictly smaller than n while keeping all earlier bits equal. The remaining lower bits may be any valid binary suffix of the remaining length, and dp[remaining_length] counts exactly those choices.

If two consecutive 1s appear in the prefix of n, then n itself and any number with the same prefix up to that point are invalid. All valid numbers smaller than n that differ earlier have already been counted, so returning immediately is correct.

If the scan completes without consecutive 1s, then n itself is valid. The algorithm adds 1 for n.

Therefore, the algorithm counts exactly the integers in [0, n] whose binary representations do not contain consecutive ones.

Complexity

Let:

L = number of bits in n

Since L = O(log n), the algorithm runs in O(log n) time.

Implementation

class Solution:
    def findIntegers(self, n: int) -> int:
        bits = bin(n)[2:]
        length = len(bits)

        dp = [0] * (length + 1)
        dp[0] = 1
        dp[1] = 2

        for i in range(2, length + 1):
            dp[i] = dp[i - 1] + dp[i - 2]

        answer = 0
        prev_bit = "0"

        for i, bit in enumerate(bits):
            remaining = length - i - 1

            if bit == "1":
                answer += dp[remaining]

                if prev_bit == "1":
                    return answer

            prev_bit = bit

        return answer + 1

Code Explanation

We first get the binary representation:

bits = bin(n)[2:]

For example:

n = 5
bits = "101"

The DP table stores the number of valid binary strings for each length:

dp[0] = 1
dp[1] = 2

There is one valid string of length 0: the empty suffix.

There are two valid strings of length 1: 0 and 1.

Then:

dp[i] = dp[i - 1] + dp[i - 2]

counts valid strings of length i.

The scan starts with:

answer = 0
prev_bit = "0"

For each 1 bit:

answer += dp[remaining]

This counts all valid numbers that are smaller than n by putting 0 at this bit.

If we see consecutive ones:

if prev_bit == "1":
    return answer

we stop because n itself is invalid.

If the loop finishes, n has no consecutive ones, so we add 1:

return answer + 1

Digit DP Alternative

We can also solve this with memoized digit DP.

The state is:

position, previous_bit, tight

where tight means the current prefix is still equal to the prefix of n.

from functools import cache

class Solution:
    def findIntegers(self, n: int) -> int:
        bits = bin(n)[2:]

        @cache
        def dfs(i: int, prev: int, tight: bool) -> int:
            if i == len(bits):
                return 1

            limit = int(bits[i]) if tight else 1
            total = 0

            for bit in range(limit + 1):
                if prev == 1 and bit == 1:
                    continue

                total += dfs(
                    i + 1,
                    bit,
                    tight and bit == limit,
                )

            return total

        return dfs(0, 0, True)

This version is easier to generalize to other digit DP problems.

Testing

def run_tests():
    s = Solution()

    assert s.findIntegers(0) == 1
    assert s.findIntegers(1) == 2
    assert s.findIntegers(2) == 3
    assert s.findIntegers(3) == 3
    assert s.findIntegers(4) == 4
    assert s.findIntegers(5) == 5
    assert s.findIntegers(6) == 5
    assert s.findIntegers(7) == 5
    assert s.findIntegers(8) == 6
    assert s.findIntegers(9) == 7

    print("all tests passed")

run_tests()

Test meaning: