What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Dynamic Programming

Builds on Linear DP and Digit Manipulation, which you haven’t finished yet.

P3HardMental model~6 min speedrun

Number of Digit One (LC 233)(opens leetcode.com)

Add up how many times the digit 1 is written across all the whole numbers from 0 to n, both ends included. A number with several 1s, such as 11, counts each of them.

Example 1

Input:n = 13

Output:6

The 1s are in 1, 10, 11 (two of them), 12 and 13: 6 in all.

Digit DP

limit n ➔ fill digits left to right with a tight flag ➔ count

Spot it when: You must count how many numbers up to a huge limit n (up to 10^9 or more) share some digit property: how many contain a 1, how many can be written from a given digit set, how many have no repeated digit. Checking each number one by one is far too slow.

Digit DP

Python

1	from functools import lru_cache
2
3	def count_digit_one(n: int) -> int:
4	"""Number of Digit One: digit DP over the digits of n, keeping whether the prefix still equals n's.
5	Time: O(D^2 * 10) \| Space: O(D^2)
6	"""
7	# digits: n's digits, most significant first; size is how many digit positions the walk fills
8	digits = [int(c) for c in str(n)]
9	size = len(digits)
10
11	@lru_cache(maxsize=None)
12	def count(pos: int, ones: int, tight: bool) -> int:
13	"""The 1s in every number that finishes this prefix, which already holds `ones` 1s."""
14	# 1. Finish A Number:
15	# Every digit is placed; the finished number contributes the 1 digits it already holds.
16	if pos == size:
17	return ones
18	# 2. Cap This Digit While Tight:
19	# tight means the prefix still equals n's digits, so this digit may not pass n's digit here.
20	top = digits[pos] if tight else 9
21	total = 0
22	for d in range(top + 1):
23	# 3. Place Digit d And Stay Tight Only On n's Own Digit:
24	# A digit below top makes every later digit free (0-9), so tight must carry forward only
25	# when it was already tight and d matches n's digit exactly here.
26	total += count(pos + 1, ones + (d == 1), tight and d == top)
27	return total
28
29	return count(0, 0, True)

Invariant: count(pos, ones, tight) is the number of 1s in every number that finishes a prefix of length pos holding ones 1s so far, and tight is true exactly when that prefix still equals n's digits.

Build every number up to n digit by digit, from the most significant digit, and keep one bit of history about the limit: tight, whether the digits placed so far equal n's. While tight, the next digit may not pass n's digit there; once a smaller digit has been placed, every later digit is free from 0 to 9. Add whatever extra fact the question needs to the state, here ones, the count of 1 digits placed so far, and memoize on the whole state: count(pos, ones, tight). This is correct because two prefixes with the same (position, extra fact, tight) finish in exactly the same set of ways, so each state needs solving only once, and the base case at pos == size reads off the answer for a finished number. The trap is the tight bit: the next position stays tight only when tight and d == top, never d == top alone. Dropping the tight and part re-caps a number that is already smaller than n, undercounting it.

See it run

Digit DP for n = 13, step by step

pos 0ones 0tight True

Each column is a digit position, and the last column is a finished number. The digit row is the digit placed. In the tight row, T means the prefix still equals the start of n. The ones row counts the 1s placed.

top the digit that caps a tight call
call the current call
cached an answer taken from lru_cache
base a finished number, which returns ones
return the total returned by a call
answer the final result

count(0, 0, True) has tight = True, so top = digits[0] = 1. The digit d runs from 0 to 1.

1top

digit

tight

Tcall

ones

1 / 21

Gotchas1 of 4

The trap
Gotcha 1: Writing d == top instead of tight and d == top
Mistake
```
total += count(pos + 1, ones + (d == 1), d == top)
```
Fix
```
total += count(pos + 1, ones + (d == 1), tight and d == top)
```
What happens: Once a digit below n's digit is placed, the number is already smaller than n. Every later digit is then free from 0 to 9. With d == top alone, a later 9 sets tight to True again. The next digit is then capped at n's digit, and some numbers are never counted.
Example: n = 100
Mistake: returns 20Fix: returns 21
Gotcha 2: Writing top = 9 without checking tight
Mistake
```
top = 9
```
Fix
```
top = digits[pos] if tight else 9
```
What happens: While tight is True, the digits placed so far equal n's digits. The next digit may not be larger than digits[pos]. With top = 9, the walk also builds numbers larger than n and counts their 1s.
Example: n = 13
Mistake: returns 20Fix: returns 6
Gotcha 3: Leaving ones out of the memo key
Mistake
```
memo[(pos, tight)] = total
```
Fix
```
memo[(pos, ones, tight)] = total
```
What happens: The base case returns ones, so the total depends on ones. A key of (pos, tight) treats two prefixes with different counts of 1s as the same state. The second prefix then gets the total stored for the first one.
Example: n = 20
Mistake: returns 2Fix: returns 12
Gotcha 4: Counting a range [lo, hi] with one call
Mistake
```
count_digit_one(hi)
```
Fix
```
count_digit_one(hi) - count_digit_one(lo - 1)
```
What happens: The walk counts every number from 0 up to its limit. It has no lower limit. For a range from lo to hi, count up to hi and subtract the count up to lo - 1.
Example: lo = 10, hi = 13
Mistake: returns 6Fix: returns 5

Not this one if…

You read or rebuild the digits of one given number, as in Palindrome Number (LC 9): nothing is counted over every number up to a limit, so there is no tight flag and no memo, only a digit loop. See Digit Manipulation

Deep Dive

What tight means and why one bit is enough

The walk builds a number from its most significant digit. We want every number from 0 to n. A number is allowed only if it is not larger than n.

While the digits placed so far equal the first digits of n, the next digit may not pass digits[pos]. This is the tight case. Once a placed digit is smaller than n's digit at that position, the number is already smaller than n. Every later digit is free from 0 to 9, whatever n says.

So the whole history of the prefix is reduced to one bit: is it still equal to n's prefix? The next tight value is tight and d == top. It stays True only when the walk was tight and the digit equals the top.

Why two prefixes can share one answer

Two different prefixes with the same pos, the same ones and the same tight have the same possible endings. The digits still to place, and the limit on each, depend only on pos and tight. The number of 1s still to count is the same, and the 1s already placed are in ones.

So count(pos, ones, tight) returns the same value for both, and lru_cache stores it once. This replaces a search over all numbers up to n by a search over states.

Example: n = 13, so digits = [1, 3]. The call count(0, 0, True) places 0 or 1 at position 0. Placing 0 leads to count(1, 0, False), which counts the numbers 0 to 9 and returns 1. Placing 1 leads to count(1, 1, True), which places 0 to 3 and returns 1 + 2 + 1 + 1 = 5. The total is 1 + 5 = 6. The 1s in 1, 10, 11, 12 and 13 are 1, 1, 2, 1 and 1, which also give 6.

The cost: states times work per state

Let D be the number of digits of n. pos has D + 1 values, ones has at most D + 1 values, and tight has 2. So there are about 2 * (D + 1) * (D + 1) states at most. Each state loops over at most 10 digits. The time is O(D^2 * 10) and the space is O(D^2).

Example: for n = 1000000000, D = 10, and the bound is 242 states. A run of the card's code creates 66 states and returns 900000001. Going through each number from 0 to n would need one billion and one steps.

The cost grows with the number of digits, not with the value of n. This is why the method works for a limit as large as 10^9 or more.

Choosing what goes into the state

The state holds the extra fact that the question needs. For Number of Digit One (LC 233), the fact is ones, the count of 1 digits so far.

For Numbers At Most N Given Digit Set (LC 902), the fact is whether the number has started. For Numbers With Repeated Digits (LC 1012), the fact is the set of digits used, written as a bitmask.

In the card's code, leading zeros are placed as the digit 0, so each number is padded with zeros on the left. A zero does not change ones, so the padding is harmless here. If a zero matters, for example when you count distinct digits, add a started flag to the state.

60-Second Pitch

"Checking each number up to n takes n steps, which is too slow for 10^9. So I build numbers digit by digit from the left and count them in groups. The state is (pos, ones, tight). tight says whether the prefix still equals n's prefix. While tight, the next digit is at most digits[pos]. After a smaller digit, every later digit is free, from 0 to 9. The next tight value is tight and d == top. Two prefixes with the same state have the same endings, so I memoize with lru_cache. There are about D squared states with 10 digits to try each. That gives O(D^2 * 10) time, which is a few hundred operations for a limit of 10^9."

Common Questions

Why is the tight flag needed?: Without it, the walk cannot know whether the next digit may be larger than n's digit. While the prefix equals n's prefix, a larger digit would create a number above n. After a smaller digit, any digit is allowed. One boolean stores this fact, and the number of states stays small.
What is the time and space complexity?: O(D^2 * 10) time and O(D^2) space, where D is the number of digits of n. There are about 2 * (D + 1) * (D + 1) states and each tries at most 10 digits. It depends on the number of digits, so it grows with the logarithm of n.
How do you count numbers in a range [a, b]?: Compute the answer for b and subtract the answer for a - 1. Both calls use the same function. If a is 0, the second count is 0.
When do you need a started flag?: You need it when a leading zero changes the answer. In the card's code, numbers are padded with zeros on the left, and a 0 does not change the count of 1s. For a rule such as no repeated digit, 007 would be treated as having a repeated 0, so you add started, which becomes True when the first non-zero digit is placed.
How do you solve Numbers At Most N Given Digit Set (LC 902) or Numbers With Repeated Digits (LC 1012) with this card?: Keep the same walk over n's digits and the same tight flag. Change the digits that may be placed: only the given set in LC 902, or any digit in LC 1012. Change the extra fact: started for LC 902, and a bitmask of used digits for LC 1012. For LC 1012, it is often easier to count the numbers with no repeated digit and subtract from n.

SWE Reasoning

Spot it

The question asks how many numbers up to a limit n have a digit property, and n is as large as 10^9 or more.
Checking every number from 0 to n is too slow, but the number of digits is small, about 10 to 19.
The property can be decided one digit at a time, with a small amount of memory about the digits placed so far.
The question uses words such as "contains a digit", "no repeated digit", "digit sum" or "written with these digits".
A range [a, b] is asked: count up to b and subtract the count up to a - 1.

The invariant, step by step

digits holds n's digits from the most significant one, and size is their number.
count(pos, ones, tight) is called. The prefix has pos digits, it contains ones 1s, and tight says whether it equals n's first pos digits.
If pos == size, the number is finished and the function returns ones.
Otherwise it sets top = digits[pos] when tight, or 9 when not tight. A digit above top would make the number larger than n.
For each d from 0 to top, it adds count(pos + 1, ones + (d == 1), tight and d == top).
The new tight is True only if the old one was True and d equals top. Any smaller digit frees every later position.
The result of the first call, count(0, 0, True), is the number of 1s in all numbers from 0 to n.

Traps

d == top without tight. After a smaller digit is placed, a later digit equal to n's digit sets tight to True again, and the next digit is capped. Some numbers are not counted. For n = 100, the result is 20 instead of 21.
top = 9 while tight. The walk builds numbers larger than n. For n = 13, the result is 20 instead of 6.
Missing ones in the state or in the key. If the count is not part of the call, two prefixes with different counts share one stored value, and the result is wrong.
Leading zeros that matter. A property such as distinct digits treats 007 differently from 7. Add a started flag, or the padded zeros are counted as digits.
Off by one on a range. To count in [a, b], compute the count for b and subtract the count for a - 1. Using a removes a itself, which is wrong.

Practice

Canonical LeetCode:Number of Digit One (LC 233)Numbers At Most N Given Digit Set (LC 902)Numbers With Repeated Digits (LC 1012)Count Special Integers (LC 2376)

Theory Context•Dynamic Programming

Builds on Linear DP and Digit Manipulation, which you haven’t finished yet.

P3HardMental model~6 min speedrun

Number of Digit One (LC 233)(opens leetcode.com)

Add up how many times the digit 1 is written across all the whole numbers from 0 to n, both ends included. A number with several 1s, such as 11, counts each of them.

Example 1

Input:n = 13

Output:6

The 1s are in 1, 10, 11 (two of them), 12 and 13: 6 in all.

Digit DP

limit n ➔ fill digits left to right with a tight flag ➔ count

Digit DP

Python

1	from functools import lru_cache
2
3	def count_digit_one(n: int) -> int:
4	"""Number of Digit One: digit DP over the digits of n, keeping whether the prefix still equals n's.
5	Time: O(D^2 * 10) \| Space: O(D^2)
6	"""
7	# digits: n's digits, most significant first; size is how many digit positions the walk fills
8	digits = [int(c) for c in str(n)]
9	size = len(digits)
10
11	@lru_cache(maxsize=None)
12	def count(pos: int, ones: int, tight: bool) -> int:
13	"""The 1s in every number that finishes this prefix, which already holds `ones` 1s."""
14	# 1. Finish A Number:
15	# Every digit is placed; the finished number contributes the 1 digits it already holds.
16	if pos == size:
17	return ones
18	# 2. Cap This Digit While Tight:
19	# tight means the prefix still equals n's digits, so this digit may not pass n's digit here.
20	top = digits[pos] if tight else 9
21	total = 0
22	for d in range(top + 1):
23	# 3. Place Digit d And Stay Tight Only On n's Own Digit:
24	# A digit below top makes every later digit free (0-9), so tight must carry forward only
25	# when it was already tight and d matches n's digit exactly here.
26	total += count(pos + 1, ones + (d == 1), tight and d == top)
27	return total
28
29	return count(0, 0, True)

See it run

Digit DP for n = 13, step by step

pos 0ones 0tight True

top the digit that caps a tight call
call the current call
cached an answer taken from lru_cache
base a finished number, which returns ones
return the total returned by a call
answer the final result

count(0, 0, True) has tight = True, so top = digits[0] = 1. The digit d runs from 0 to 1.

1top

digit

tight

Tcall

ones

1 / 21

Gotchas1 of 4

The trap
Gotcha 1: Writing d == top instead of tight and d == top
Mistake
```
total += count(pos + 1, ones + (d == 1), d == top)
```
Fix
```
total += count(pos + 1, ones + (d == 1), tight and d == top)
```
What happens: Once a digit below n's digit is placed, the number is already smaller than n. Every later digit is then free from 0 to 9. With d == top alone, a later 9 sets tight to True again. The next digit is then capped at n's digit, and some numbers are never counted.
Example: n = 100
Mistake: returns 20Fix: returns 21
Gotcha 2: Writing top = 9 without checking tight
Mistake
```
top = 9
```
Fix
```
top = digits[pos] if tight else 9
```
What happens: While tight is True, the digits placed so far equal n's digits. The next digit may not be larger than digits[pos]. With top = 9, the walk also builds numbers larger than n and counts their 1s.
Example: n = 13
Mistake: returns 20Fix: returns 6
Gotcha 3: Leaving ones out of the memo key
Mistake
```
memo[(pos, tight)] = total
```
Fix
```
memo[(pos, ones, tight)] = total
```
What happens: The base case returns ones, so the total depends on ones. A key of (pos, tight) treats two prefixes with different counts of 1s as the same state. The second prefix then gets the total stored for the first one.
Example: n = 20
Mistake: returns 2Fix: returns 12
Gotcha 4: Counting a range [lo, hi] with one call
Mistake
```
count_digit_one(hi)
```
Fix
```
count_digit_one(hi) - count_digit_one(lo - 1)
```
What happens: The walk counts every number from 0 up to its limit. It has no lower limit. For a range from lo to hi, count up to hi and subtract the count up to lo - 1.
Example: lo = 10, hi = 13
Mistake: returns 6Fix: returns 5

Not this one if…

You read or rebuild the digits of one given number, as in Palindrome Number (LC 9): nothing is counted over every number up to a limit, so there is no tight flag and no memo, only a digit loop. See Digit Manipulation

Deep Dive

What tight means and why one bit is enough

The walk builds a number from its most significant digit. We want every number from 0 to n. A number is allowed only if it is not larger than n.

Why two prefixes can share one answer

So count(pos, ones, tight) returns the same value for both, and lru_cache stores it once. This replaces a search over all numbers up to n by a search over states.

The cost: states times work per state

The cost grows with the number of digits, not with the value of n. This is why the method works for a limit as large as 10^9 or more.

Choosing what goes into the state

The state holds the extra fact that the question needs. For Number of Digit One (LC 233), the fact is ones, the count of 1 digits so far.

For Numbers At Most N Given Digit Set (LC 902), the fact is whether the number has started. For Numbers With Repeated Digits (LC 1012), the fact is the set of digits used, written as a bitmask.

60-Second Pitch

Common Questions

Why is the tight flag needed?: Without it, the walk cannot know whether the next digit may be larger than n's digit. While the prefix equals n's prefix, a larger digit would create a number above n. After a smaller digit, any digit is allowed. One boolean stores this fact, and the number of states stays small.
What is the time and space complexity?: O(D^2 * 10) time and O(D^2) space, where D is the number of digits of n. There are about 2 * (D + 1) * (D + 1) states and each tries at most 10 digits. It depends on the number of digits, so it grows with the logarithm of n.
How do you count numbers in a range [a, b]?: Compute the answer for b and subtract the answer for a - 1. Both calls use the same function. If a is 0, the second count is 0.
When do you need a started flag?: You need it when a leading zero changes the answer. In the card's code, numbers are padded with zeros on the left, and a 0 does not change the count of 1s. For a rule such as no repeated digit, 007 would be treated as having a repeated 0, so you add started, which becomes True when the first non-zero digit is placed.
How do you solve Numbers At Most N Given Digit Set (LC 902) or Numbers With Repeated Digits (LC 1012) with this card?: Keep the same walk over n's digits and the same tight flag. Change the digits that may be placed: only the given set in LC 902, or any digit in LC 1012. Change the extra fact: started for LC 902, and a bitmask of used digits for LC 1012. For LC 1012, it is often easier to count the numbers with no repeated digit and subtract from n.

SWE Reasoning

Spot it

The question asks how many numbers up to a limit n have a digit property, and n is as large as 10^9 or more.
Checking every number from 0 to n is too slow, but the number of digits is small, about 10 to 19.
The property can be decided one digit at a time, with a small amount of memory about the digits placed so far.
The question uses words such as "contains a digit", "no repeated digit", "digit sum" or "written with these digits".
A range [a, b] is asked: count up to b and subtract the count up to a - 1.

The invariant, step by step

digits holds n's digits from the most significant one, and size is their number.
count(pos, ones, tight) is called. The prefix has pos digits, it contains ones 1s, and tight says whether it equals n's first pos digits.
If pos == size, the number is finished and the function returns ones.
Otherwise it sets top = digits[pos] when tight, or 9 when not tight. A digit above top would make the number larger than n.
For each d from 0 to top, it adds count(pos + 1, ones + (d == 1), tight and d == top).
The new tight is True only if the old one was True and d equals top. Any smaller digit frees every later position.
The result of the first call, count(0, 0, True), is the number of 1s in all numbers from 0 to n.

Traps

d == top without tight. After a smaller digit is placed, a later digit equal to n's digit sets tight to True again, and the next digit is capped. Some numbers are not counted. For n = 100, the result is 20 instead of 21.
top = 9 while tight. The walk builds numbers larger than n. For n = 13, the result is 20 instead of 6.
Missing ones in the state or in the key. If the count is not part of the call, two prefixes with different counts share one stored value, and the result is wrong.
Leading zeros that matter. A property such as distinct digits treats 007 differently from 7. Add a started flag, or the padded zeros are counted as digits.
Off by one on a range. To count in [a, b], compute the count for b and subtract the count for a - 1. Using a removes a itself, which is wrong.

Practice

Canonical LeetCode:Number of Digit One (LC 233)Numbers At Most N Given Digit Set (LC 902)Numbers With Repeated Digits (LC 1012)Count Special Integers (LC 2376)

Theory Context•Dynamic Programming

Builds on Linear DP and Digit Manipulation, which you haven’t finished yet.

P3HardMental model~6 min speedrun

Number of Digit One (LC 233)(opens leetcode.com)

Add up how many times the digit 1 is written across all the whole numbers from 0 to n, both ends included. A number with several 1s, such as 11, counts each of them.

Example 1

Input:n = 13

Output:6

The 1s are in 1, 10, 11 (two of them), 12 and 13: 6 in all.

Digit DP

limit n ➔ fill digits left to right with a tight flag ➔ count

Digit DP

Python

1	from functools import lru_cache
2
3	def count_digit_one(n: int) -> int:
4	"""Number of Digit One: digit DP over the digits of n, keeping whether the prefix still equals n's.
5	Time: O(D^2 * 10) \| Space: O(D^2)
6	"""
7	# digits: n's digits, most significant first; size is how many digit positions the walk fills
8	digits = [int(c) for c in str(n)]
9	size = len(digits)
10
11	@lru_cache(maxsize=None)
12	def count(pos: int, ones: int, tight: bool) -> int:
13	"""The 1s in every number that finishes this prefix, which already holds `ones` 1s."""
14	# 1. Finish A Number:
15	# Every digit is placed; the finished number contributes the 1 digits it already holds.
16	if pos == size:
17	return ones
18	# 2. Cap This Digit While Tight:
19	# tight means the prefix still equals n's digits, so this digit may not pass n's digit here.
20	top = digits[pos] if tight else 9
21	total = 0
22	for d in range(top + 1):
23	# 3. Place Digit d And Stay Tight Only On n's Own Digit:
24	# A digit below top makes every later digit free (0-9), so tight must carry forward only
25	# when it was already tight and d matches n's digit exactly here.
26	total += count(pos + 1, ones + (d == 1), tight and d == top)
27	return total
28
29	return count(0, 0, True)

See it run

Digit DP for n = 13, step by step

pos 0ones 0tight True

top the digit that caps a tight call
call the current call
cached an answer taken from lru_cache
base a finished number, which returns ones
return the total returned by a call
answer the final result

count(0, 0, True) has tight = True, so top = digits[0] = 1. The digit d runs from 0 to 1.

1top

digit

tight

Tcall

ones

1 / 21

Gotchas1 of 4

The trap
Gotcha 1: Writing d == top instead of tight and d == top
Mistake
```
total += count(pos + 1, ones + (d == 1), d == top)
```
Fix
```
total += count(pos + 1, ones + (d == 1), tight and d == top)
```
What happens: Once a digit below n's digit is placed, the number is already smaller than n. Every later digit is then free from 0 to 9. With d == top alone, a later 9 sets tight to True again. The next digit is then capped at n's digit, and some numbers are never counted.
Example: n = 100
Mistake: returns 20Fix: returns 21
Gotcha 2: Writing top = 9 without checking tight
Mistake
```
top = 9
```
Fix
```
top = digits[pos] if tight else 9
```
What happens: While tight is True, the digits placed so far equal n's digits. The next digit may not be larger than digits[pos]. With top = 9, the walk also builds numbers larger than n and counts their 1s.
Example: n = 13
Mistake: returns 20Fix: returns 6
Gotcha 3: Leaving ones out of the memo key
Mistake
```
memo[(pos, tight)] = total
```
Fix
```
memo[(pos, ones, tight)] = total
```
What happens: The base case returns ones, so the total depends on ones. A key of (pos, tight) treats two prefixes with different counts of 1s as the same state. The second prefix then gets the total stored for the first one.
Example: n = 20
Mistake: returns 2Fix: returns 12
Gotcha 4: Counting a range [lo, hi] with one call
Mistake
```
count_digit_one(hi)
```
Fix
```
count_digit_one(hi) - count_digit_one(lo - 1)
```
What happens: The walk counts every number from 0 up to its limit. It has no lower limit. For a range from lo to hi, count up to hi and subtract the count up to lo - 1.
Example: lo = 10, hi = 13
Mistake: returns 6Fix: returns 5

Not this one if…

You read or rebuild the digits of one given number, as in Palindrome Number (LC 9): nothing is counted over every number up to a limit, so there is no tight flag and no memo, only a digit loop. See Digit Manipulation

Deep Dive

What tight means and why one bit is enough

The walk builds a number from its most significant digit. We want every number from 0 to n. A number is allowed only if it is not larger than n.

Why two prefixes can share one answer

So count(pos, ones, tight) returns the same value for both, and lru_cache stores it once. This replaces a search over all numbers up to n by a search over states.

The cost: states times work per state

The cost grows with the number of digits, not with the value of n. This is why the method works for a limit as large as 10^9 or more.

Choosing what goes into the state

The state holds the extra fact that the question needs. For Number of Digit One (LC 233), the fact is ones, the count of 1 digits so far.

For Numbers At Most N Given Digit Set (LC 902), the fact is whether the number has started. For Numbers With Repeated Digits (LC 1012), the fact is the set of digits used, written as a bitmask.

60-Second Pitch

Common Questions

Why is the tight flag needed?: Without it, the walk cannot know whether the next digit may be larger than n's digit. While the prefix equals n's prefix, a larger digit would create a number above n. After a smaller digit, any digit is allowed. One boolean stores this fact, and the number of states stays small.
What is the time and space complexity?: O(D^2 * 10) time and O(D^2) space, where D is the number of digits of n. There are about 2 * (D + 1) * (D + 1) states and each tries at most 10 digits. It depends on the number of digits, so it grows with the logarithm of n.
How do you count numbers in a range [a, b]?: Compute the answer for b and subtract the answer for a - 1. Both calls use the same function. If a is 0, the second count is 0.
When do you need a started flag?: You need it when a leading zero changes the answer. In the card's code, numbers are padded with zeros on the left, and a 0 does not change the count of 1s. For a rule such as no repeated digit, 007 would be treated as having a repeated 0, so you add started, which becomes True when the first non-zero digit is placed.
How do you solve Numbers At Most N Given Digit Set (LC 902) or Numbers With Repeated Digits (LC 1012) with this card?: Keep the same walk over n's digits and the same tight flag. Change the digits that may be placed: only the given set in LC 902, or any digit in LC 1012. Change the extra fact: started for LC 902, and a bitmask of used digits for LC 1012. For LC 1012, it is often easier to count the numbers with no repeated digit and subtract from n.

SWE Reasoning

Spot it

The question asks how many numbers up to a limit n have a digit property, and n is as large as 10^9 or more.
Checking every number from 0 to n is too slow, but the number of digits is small, about 10 to 19.
The property can be decided one digit at a time, with a small amount of memory about the digits placed so far.
The question uses words such as "contains a digit", "no repeated digit", "digit sum" or "written with these digits".
A range [a, b] is asked: count up to b and subtract the count up to a - 1.

The invariant, step by step

digits holds n's digits from the most significant one, and size is their number.
count(pos, ones, tight) is called. The prefix has pos digits, it contains ones 1s, and tight says whether it equals n's first pos digits.
If pos == size, the number is finished and the function returns ones.
Otherwise it sets top = digits[pos] when tight, or 9 when not tight. A digit above top would make the number larger than n.
For each d from 0 to top, it adds count(pos + 1, ones + (d == 1), tight and d == top).
The new tight is True only if the old one was True and d equals top. Any smaller digit frees every later position.
The result of the first call, count(0, 0, True), is the number of 1s in all numbers from 0 to n.

Traps

d == top without tight. After a smaller digit is placed, a later digit equal to n's digit sets tight to True again, and the next digit is capped. Some numbers are not counted. For n = 100, the result is 20 instead of 21.
top = 9 while tight. The walk builds numbers larger than n. For n = 13, the result is 20 instead of 6.
Missing ones in the state or in the key. If the count is not part of the call, two prefixes with different counts share one stored value, and the result is wrong.
Leading zeros that matter. A property such as distinct digits treats 007 differently from 7. Add a started flag, or the padded zeros are counted as digits.
Off by one on a range. To count in [a, b], compute the count for b and subtract the count for a - 1. Using a removes a itself, which is wrong.

Practice

Canonical LeetCode:Number of Digit One (LC 233)Numbers At Most N Given Digit Set (LC 902)Numbers With Repeated Digits (LC 1012)Count Special Integers (LC 2376)

Theory Context•Dynamic Programming

Builds on Linear DP and Digit Manipulation, which you haven’t finished yet.

P3HardMental model~6 min speedrun

Number of Digit One (LC 233)(opens leetcode.com)

Add up how many times the digit 1 is written across all the whole numbers from 0 to n, both ends included. A number with several 1s, such as 11, counts each of them.

Example 1

Input:n = 13

Output:6

The 1s are in 1, 10, 11 (two of them), 12 and 13: 6 in all.

Digit DP

limit n ➔ fill digits left to right with a tight flag ➔ count

Digit DP

Python

1	from functools import lru_cache
2
3	def count_digit_one(n: int) -> int:
4	"""Number of Digit One: digit DP over the digits of n, keeping whether the prefix still equals n's.
5	Time: O(D^2 * 10) \| Space: O(D^2)
6	"""
7	# digits: n's digits, most significant first; size is how many digit positions the walk fills
8	digits = [int(c) for c in str(n)]
9	size = len(digits)
10
11	@lru_cache(maxsize=None)
12	def count(pos: int, ones: int, tight: bool) -> int:
13	"""The 1s in every number that finishes this prefix, which already holds `ones` 1s."""
14	# 1. Finish A Number:
15	# Every digit is placed; the finished number contributes the 1 digits it already holds.
16	if pos == size:
17	return ones
18	# 2. Cap This Digit While Tight:
19	# tight means the prefix still equals n's digits, so this digit may not pass n's digit here.
20	top = digits[pos] if tight else 9
21	total = 0
22	for d in range(top + 1):
23	# 3. Place Digit d And Stay Tight Only On n's Own Digit:
24	# A digit below top makes every later digit free (0-9), so tight must carry forward only
25	# when it was already tight and d matches n's digit exactly here.
26	total += count(pos + 1, ones + (d == 1), tight and d == top)
27	return total
28
29	return count(0, 0, True)

See it run

Digit DP for n = 13, step by step

pos 0ones 0tight True

top the digit that caps a tight call
call the current call
cached an answer taken from lru_cache
base a finished number, which returns ones
return the total returned by a call
answer the final result

count(0, 0, True) has tight = True, so top = digits[0] = 1. The digit d runs from 0 to 1.

1top

digit

tight

Tcall

ones

1 / 21

Gotchas1 of 4

The trap
Gotcha 1: Writing d == top instead of tight and d == top
Mistake
```
total += count(pos + 1, ones + (d == 1), d == top)
```
Fix
```
total += count(pos + 1, ones + (d == 1), tight and d == top)
```
What happens: Once a digit below n's digit is placed, the number is already smaller than n. Every later digit is then free from 0 to 9. With d == top alone, a later 9 sets tight to True again. The next digit is then capped at n's digit, and some numbers are never counted.
Example: n = 100
Mistake: returns 20Fix: returns 21
Gotcha 2: Writing top = 9 without checking tight
Mistake
```
top = 9
```
Fix
```
top = digits[pos] if tight else 9
```
What happens: While tight is True, the digits placed so far equal n's digits. The next digit may not be larger than digits[pos]. With top = 9, the walk also builds numbers larger than n and counts their 1s.
Example: n = 13
Mistake: returns 20Fix: returns 6
Gotcha 3: Leaving ones out of the memo key
Mistake
```
memo[(pos, tight)] = total
```
Fix
```
memo[(pos, ones, tight)] = total
```
What happens: The base case returns ones, so the total depends on ones. A key of (pos, tight) treats two prefixes with different counts of 1s as the same state. The second prefix then gets the total stored for the first one.
Example: n = 20
Mistake: returns 2Fix: returns 12
Gotcha 4: Counting a range [lo, hi] with one call
Mistake
```
count_digit_one(hi)
```
Fix
```
count_digit_one(hi) - count_digit_one(lo - 1)
```
What happens: The walk counts every number from 0 up to its limit. It has no lower limit. For a range from lo to hi, count up to hi and subtract the count up to lo - 1.
Example: lo = 10, hi = 13
Mistake: returns 6Fix: returns 5

Not this one if…

You read or rebuild the digits of one given number, as in Palindrome Number (LC 9): nothing is counted over every number up to a limit, so there is no tight flag and no memo, only a digit loop. See Digit Manipulation

Deep Dive

What tight means and why one bit is enough

The walk builds a number from its most significant digit. We want every number from 0 to n. A number is allowed only if it is not larger than n.

Why two prefixes can share one answer

So count(pos, ones, tight) returns the same value for both, and lru_cache stores it once. This replaces a search over all numbers up to n by a search over states.

The cost: states times work per state

The cost grows with the number of digits, not with the value of n. This is why the method works for a limit as large as 10^9 or more.

Choosing what goes into the state

The state holds the extra fact that the question needs. For Number of Digit One (LC 233), the fact is ones, the count of 1 digits so far.

For Numbers At Most N Given Digit Set (LC 902), the fact is whether the number has started. For Numbers With Repeated Digits (LC 1012), the fact is the set of digits used, written as a bitmask.

60-Second Pitch

Common Questions

Why is the tight flag needed?: Without it, the walk cannot know whether the next digit may be larger than n's digit. While the prefix equals n's prefix, a larger digit would create a number above n. After a smaller digit, any digit is allowed. One boolean stores this fact, and the number of states stays small.
What is the time and space complexity?: O(D^2 * 10) time and O(D^2) space, where D is the number of digits of n. There are about 2 * (D + 1) * (D + 1) states and each tries at most 10 digits. It depends on the number of digits, so it grows with the logarithm of n.
How do you count numbers in a range [a, b]?: Compute the answer for b and subtract the answer for a - 1. Both calls use the same function. If a is 0, the second count is 0.
When do you need a started flag?: You need it when a leading zero changes the answer. In the card's code, numbers are padded with zeros on the left, and a 0 does not change the count of 1s. For a rule such as no repeated digit, 007 would be treated as having a repeated 0, so you add started, which becomes True when the first non-zero digit is placed.
How do you solve Numbers At Most N Given Digit Set (LC 902) or Numbers With Repeated Digits (LC 1012) with this card?: Keep the same walk over n's digits and the same tight flag. Change the digits that may be placed: only the given set in LC 902, or any digit in LC 1012. Change the extra fact: started for LC 902, and a bitmask of used digits for LC 1012. For LC 1012, it is often easier to count the numbers with no repeated digit and subtract from n.

SWE Reasoning

Spot it

The question asks how many numbers up to a limit n have a digit property, and n is as large as 10^9 or more.
Checking every number from 0 to n is too slow, but the number of digits is small, about 10 to 19.
The property can be decided one digit at a time, with a small amount of memory about the digits placed so far.
The question uses words such as "contains a digit", "no repeated digit", "digit sum" or "written with these digits".
A range [a, b] is asked: count up to b and subtract the count up to a - 1.

The invariant, step by step

digits holds n's digits from the most significant one, and size is their number.
count(pos, ones, tight) is called. The prefix has pos digits, it contains ones 1s, and tight says whether it equals n's first pos digits.
If pos == size, the number is finished and the function returns ones.
Otherwise it sets top = digits[pos] when tight, or 9 when not tight. A digit above top would make the number larger than n.
For each d from 0 to top, it adds count(pos + 1, ones + (d == 1), tight and d == top).
The new tight is True only if the old one was True and d equals top. Any smaller digit frees every later position.
The result of the first call, count(0, 0, True), is the number of 1s in all numbers from 0 to n.

Traps

d == top without tight. After a smaller digit is placed, a later digit equal to n's digit sets tight to True again, and the next digit is capped. Some numbers are not counted. For n = 100, the result is 20 instead of 21.
top = 9 while tight. The walk builds numbers larger than n. For n = 13, the result is 20 instead of 6.
Missing ones in the state or in the key. If the count is not part of the call, two prefixes with different counts share one stored value, and the result is wrong.
Leading zeros that matter. A property such as distinct digits treats 007 differently from 7. Add a started flag, or the padded zeros are counted as digits.
Off by one on a range. To count in [a, b], compute the count for b and subtract the count for a - 1. Using a removes a itself, which is wrong.

Practice

Canonical LeetCode:Number of Digit One (LC 233)Numbers At Most N Given Digit Set (LC 902)Numbers With Repeated Digits (LC 1012)Count Special Integers (LC 2376)