Abstract / Summary

Count numbers with no two ones next to each other in their binary form.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 42% (100k+ submissions).

Typical patterns to solve this problem:

• Dynamic Programming

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation computes the count of non-negative integers not larger than a given n whose binary representation does not contain two consecutive 1s. It does this by converting n to its binary string, then performing a depth-first search with memoization over the positions of that string. The recursion tracks three pieces of state: the current index in the binary string, whether the previous placed digit was 1, and whether the prefix built so far is still constrained by the original upper bound. The memoization (@cache) guarantees that each distinct state is evaluated only once, turning an exponential-looking search into a linear-time solution with respect to the number of bits.

Key Steps

Binary conversion and size determination

high = "{0:b}".format(n)
size = len(high)

The integer n is rendered as a binary string high. Its length size determines how many recursive levels are required, one for each bit position from most-significant to least-significant.

Memoized recursive helper

@cache
def deeper(pos, prev, limit):
    if pos == size:
        return 1
    ...

The inner function deeper is decorated with @cache, which stores the result for each tuple (pos, prev, limit). The base case occurs when the recursion has processed all bit positions (pos == size), at which point a valid construction has been completed and contributes a count of one.

Handling the “0” choice

result = deeper(pos + 1, 0, limit and high[pos] == "0")

At every position the algorithm may always place a 0. The prev argument is reset to 0 because the most recent digit becomes 0. The limit flag is updated to remain true only if the current prefix is still equal to the prefix of high and the current bit of high is also 0. This ensures that once a smaller prefix has been chosen, subsequent positions are free from the upper-bound restriction.

Handling the “1” choice

if prev != 1:
    if high[pos] == "1" or not limit:
        result += deeper(pos + 1, 1, limit)

A 1 can be appended only when the previous digit was not 1, enforcing the “no consecutive ones” rule. The inner condition checks that adding a 1 does not exceed the original bound: either the corresponding bit in high is 1 (so the prefix stays equal) or the recursion is already unrestricted (limit is False). When allowed, the function recurses with prev set to 1 and the same limit flag, because the prefix remains tight only when the current bit of high is 1.

Final aggregation

return deeper(0, 0, True)

The initial call starts at the most-significant bit (pos = 0), with no preceding 1 (prev = 0), and with the limit active (limit = True). The returned value is the total number of admissible integers from 0 up to n.

Edge Cases Handled

When n is 0, the binary string high becomes "0" and size is 1. The recursion immediately processes the single position, allowing only the 0 branch; the base case is reached after one step, yielding a count of 1, which correctly represents the single integer 0.

If n consists entirely of 1s (for example 7 → "111"), the limit flag stays true while the algorithm explores the 0 branch at each position, but the 1 branch is permitted only when the previous digit is 0. This correctly excludes numbers like 3 ("11") that would violate the consecutive-1 rule, while still counting all valid numbers up to the bound.

When the binary representation contains a 0 after a 1 (e.g., n = 10 → "1010"), the limit flag may become False after a 0 is chosen at a position where high[pos] is 1. Once limit is False, the condition high[pos] == "1" or not limit always succeeds for the 1 branch, allowing the recursion to freely explore both 0 and 1 choices for the remaining less-significant bits without further bound checks. This correctly accounts for all numbers whose prefix is already smaller than the bound.

The prev parameter ensures that the very first digit can be 1 because the initial prev is 0. Consequently, numbers whose most-significant bit is 1 are considered, respecting the original range that includes numbers with the same bit-length as n.

Performance Optimizations

The primary optimization is the use of Python’s functools.cache (or lru_cache) on the recursive helper. By caching results for each combination of (pos, prev, limit), the algorithm avoids recomputing identical sub-problems. Since pos ranges over the bit length of n (at most 31 for 32-bit integers, or 63 for 64-bit), prev has two possible values, and limit is a boolean, the total number of distinct states is bounded by size * 2 * 2. Consequently, the recursion executes a constant number of calls per bit, yielding linear performance with respect to the number of bits.

The decision to represent n as a binary string rather than repeatedly shifting bits simplifies the limit checks. Accessing high[pos] is an O(1) operation, and the string representation avoids bitwise operations inside the recursion, which can be marginally faster in Python due to reduced arithmetic overhead.

The early pruning of the 1 branch when prev == 1 eliminates entire sub-trees that would inevitably violate the “no consecutive ones” constraint. This prevents unnecessary recursive calls and reduces the number of cached entries.

Finally, the base case returns 1 directly without further computation, allowing the recursion to unwind quickly once a full valid binary number has been constructed. This contributes to a tight recursion depth equal to the bit length, avoiding stack growth beyond what is necessary.

Imagine you are building a long train out of blocks that are either zero or one. The rule for this special train is that you are never allowed to put two blocks with a one next to each other. You want to see how many different trains you can build that are not longer than a certain number.

The code starts by looking at the number you picked and turning it into a string of zeros and ones, just like the blocks in your train. Then it starts a process to count every possible combination of blocks.

The instructions tell the computer to look at each spot for a block one by one. It tries placing a zero, and then it tries placing a one. Because of the rule, it only places a one if the block before it was a zero. It also checks to make sure the final train does not get too big based on the number you originally picked.

The code uses a special trick to remember the work it has already done so it does not have to count the same patterns over and over again. It keeps picking blocks and moving forward until the train reaches the right size. Every time it finishes a valid train, it adds that to the total count of trains you can make.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python			TS
	WalkCCC	C++		Java
	leetcode.ca	C++		Java		Python		Go	TS
	LeetcodeHelp	C++		Java		Python
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	gouthampradhan			Java
	JoshCrozier		JS
	linouk23	C++
	lkwq007					Python
	ruoru				Rust
	suxrobGM						C#
	wisdompeak	C++
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
gouthampradhan	Java
JoshCrozier	JavaScript
linouk23	C++
lkwq007	Python
ruoru	Rust
suxrobGM	C#
wisdompeak	C++
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality