Number of Digit One (LeetCode 233)
You will see how counting over every number up to n becomes a small table over (position, 1s so far, still tight).
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.
Worked Examples
n = 136n = 00⚖️Formal Constraints & Bounds
0 <= n <= 109
Why It Works & Core Invariant
Numbers up to n can be built digit by digit, and every prefix only needs three facts to finish: its position, the 1s it holds, and whether it still equals n's prefix. Same facts, same future, so each state is counted once.
Real-World Scenario & Production Applications
Counting how many IDs, invoice numbers or ticket numbers in a range contain a given digit or pattern, for example to size a lookup table or to audit a numbering scheme, is the same count: the range is far too large to scan, but its limit can be walked digit by digit.
Step-by-Step Execution Trace Table
The trap case n = 190 (digits = [1, 9, 0]), at the calls where the tight bit matters. count(pos, ones, tight) returns the 1s in every number that finishes the prefix:
| Call | top | Digits tried | What happens |
|---|---|---|---|
count(0, 0, True) | 1 | 0, 1 | The first digit is 0 (numbers below 100) or 1 (100 to 190) |
count(1, 0, False) | 9 | 0..9 | After a 0 the prefix is already smaller than 190, so every second digit is free |
count(2, 0, False) | 9 | 0..9 | With tight and d == top, a 9 in the middle keeps the last digit free: 0..9 |
count(1, 1, True) | 9 | 0..9 | Still tight after the 1: the second digit may go up to 9 |
count(2, 1, True) | 0 | 0 | Tight after 1, 9: the last digit may only be 0 (the number 190) |
| End | count(0, 0, True) = 130 |
Staying tight on d == top alone would make count(2, 0, True) after the prefix 0, 9 cap the last digit at 0, dropping 91 and returning 129.
| 1 | Build every number up to `n` digit by digit from the most significant digit, and keep `tight`: whether the digits so far equal `n`'s. |
| 2 | `count(pos, ones, tight)` is the number of 1s in every number that finishes the prefix; a finished number adds its `ones`, and each allowed digit moves to `pos + 1`. |
| 3 | The shape: split `n` into its digits, a memoized count over (position, 1s so far, still tight), a base case at the end of the digits, a loop over the digits allowed at this position, and the call for position 0. |
| 4 | The trap: the next position is tight only when `tight and d == top`. `d == top` alone caps a number that was already smaller than `n`. |
Target: Number of Digit One (LeetCode 233). Every number up to `n` is written with as many digits as `n` (shorter ones get leading zeros), and the limit is checked one digit at a time.
Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).
Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting something over every number from 0 to n is hopeless one number at a time when n is 10^9. Digit DP builds the numbers digit by digit instead, from the most significant digit, and keeps one bit of history about the limit: tight, whether every digit so far equals n's. While tight, the next digit may not pass n's digit; once a smaller digit has been placed, every later digit is free. Add the one fact the question needs, here ones, the 1s placed so far, and the whole count is a small table over (position, ones, tight).
🔢 The Analogy: A Combination Lock With a Maximum
Think of dialling every code up to a maximum on a lock, wheel by wheel. As long as the wheels you have set match the maximum, the next wheel may only go up to the maximum's digit. The moment one wheel is set lower, the rest can spin freely from 0 to 9. You never list the codes: you count how many ways each wheel can finish.
🪄 The Mathematical Harmony / Magic Trick
@lru_cache(maxsize=None)def count(pos, ones, tight): if pos == size: return ones top = digits[pos] if tight else 9 return sum(count(pos + 1, ones + (d == 1), tight and d == top) for d in range(top + 1)) Two prefixes with the same (position, ones, tight) finish in exactly the same ways, so each state is solved once. The tight bit must pass on only when the prefix was tight and took n's digit: tight and d == top.
💡 Summary
Split the limit into digits, count over (position, the fact you need, tight), cap a digit at n's only while tight, and leave tight the moment a smaller digit is placed. About steps for a -digit n.
Staying tight on the digit alone: the next position is tight only when
tight and d == top. Usingd == topalone caps a number that was already smaller thann: after a0undern's1, a9would cap the next digit (n = 190gives 129 instead of 130).Using 9 as the top while tight:
top = digits[pos] if tight else 9. A tight prefix may not passn's digit here, or numbers abovenare counted.Counting numbers instead of 1s: the base case returns
ones, the 1s the finished number holds. Returning 1 counts the numbers, and a flag counts the numbers that contain a 1.Dropping
onesfrom the memo key:countdepends on how many 1s are already placed, so(pos, ones, tight)is the key. Caching on(pos, tight)alone reuses a total computed for a differentones.
4-Phase Thought Process Model
You will see how a senior engineer spots a count over every number up to a huge n and turns it into a walk over n's digits.
Pattern Recognition Signals
The 10-second spot
"Add up how many times the digit 1 is written across all the whole numbers from 0 to n" with n up to 10^9: a count over every number up to a limit, where the property depends only on the digits. Scanning is too slow, so walk the limit's digits: Digit DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
count(pos, ones, tight) is the number of 1s in every number that finishes a prefix of length pos holding ones 1s, where tight means the prefix equals n's. top = digits[pos] if tight else 9; each d in range(top + 1) moves to count(pos + 1, ones + (d == 1), tight and d == top); count(size, ones, _) = ones; the answer is count(0, 0, True).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
tight and d == top, notd == top: after a smaller digit the number is belownfor good, andd == topalone would cap it again (n = 190gives 129 instead of 130).top = digits[pos] if tight else 9: while tight the digit may not passn's, or numbers abovenare counted.The base case returns
ones, not 1: the question counts 1 digits, not numbers.The memo key is
(pos, ones, tight): caching on(pos, tight)alone reuses a total computed for a different number of 1s.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Digit DP. Scanning every number up to a billion is too slow, but the count only depends on the digits, so I build the numbers digit by digit from the front. A state is the position, how many 1s the prefix holds, and whether the prefix still equals n's, called tight. While tight, the next digit can only go up to n's digit there; otherwise it can be anything from 0 to 9. Each finished number adds its 1s. Prefixes with the same state finish the same way, so I memoize on all three. The trap is the tight bit: the next position stays tight only if this one was tight and took n's digit. Using the digit alone would cap a number that's already smaller than n. There are about D squared times two states with ten digits each, so O(D squared times 10) for D digits.
So: count(pos, ones, tight), top = digits[pos] if tight else 9, tight and d == top for the next position, a finished number adds ones.
Complexity & Mathematical Proof
O(D^2 * 10)
Look at the code: count is memoized on (pos, ones, tight). pos runs from 0 to D, ones from 0 to D and tight is True or False, so there are at most (D + 1)^2 * 2 states. Each state runs for d in range(top + 1), at most 10 digits, with O(1) work per digit. Total: O(D^2 * 10). For n up to 10^9, D is at most 10, so this is a few thousand steps.
O(D^2)
The lru_cache keeps one entry per state, O(D^2), and the recursion goes at most D + 1 calls deep. digits holds D digits. The answer is one integer.
Look at the code: count is memoized on (pos, ones, tight). pos runs from 0 to D, ones from 0 to D and tight is True or False, so there are at most (D + 1)^2 * 2 states. Each state runs for d in range(top + 1), at most 10 digits, with O(1) work per digit. Total: O(D^2 * 10). For n up to 10^9, D is at most 10, so this is a few thousand steps.
Derivation Progression
(D + 1) * (D + 1) * 2
pos from 0 to D, ones from 0 to D, and tight True or False; lru_cache solves each once.
at most 10 digits
for d in range(top + 1) tries at most 10 digits, each with one cached call and one addition.
O(D^2 * 10)
For n = 10^9, D = 10: at most 242 states and about 2,400 digit tries, against about 10^10 digit checks for the brute force.
Variable Definitions
The limit n
Number of digits of n (size in the code), at most 10
Memory Architecture & Bounds
O(D): the recursion goes one call per digit
O(D^2): the memo of (pos, ones, tight) states
O(1): one integer
Boundary Best / Worst Cases
for a one-digit n
with
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: **"all the whole numbers from 0 to n"**, "how many times the digit 1 is written", with n up to . A count over every number up to a limit where the property depends only on the digits: Digit DP over (position, the fact you need, tight).
, so digits. Checking every number is about digit checks; the digit walk has at most states with up to 10 digits each. The answer is below , so a 64-bit integer is needed in fixed-width languages.
Passing d == top on instead of tight and d == top re-caps numbers that are already below n. A range [lo, hi] is two runs, f(hi) - f(lo - 1), not one walk. A property that needs more history (digits used, previous digit, a running remainder) goes into the state, and the state count is what decides whether it still fits.
Core Algorithmic State Invariants
Every number up to `n` is written with `n`'s number of digits (shorter ones get leading zeros), so counting over the numbers becomes a walk over positions from the most significant digit.
`top = digits[pos] if tight else 9`, and the next position gets `tight and d == top`. Once a smaller digit is placed the number is below `n` for good; `d == top` alone would cap it again.
`count(pos, ones, tight)` depends only on those three values, so `lru_cache` solves each of about 2D^2 states once: O(D^2 * 10) time and O(D^2) space for a D-digit `n`.
Number of Digit One (LeetCode 233)
You will see how counting over every number up to n becomes a small table over (position, 1s so far, still tight).
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.
Worked Examples
n = 136n = 00⚖️Formal Constraints & Bounds
0 <= n <= 109
Why It Works & Core Invariant
Numbers up to n can be built digit by digit, and every prefix only needs three facts to finish: its position, the 1s it holds, and whether it still equals n's prefix. Same facts, same future, so each state is counted once.
Real-World Scenario & Production Applications
Counting how many IDs, invoice numbers or ticket numbers in a range contain a given digit or pattern, for example to size a lookup table or to audit a numbering scheme, is the same count: the range is far too large to scan, but its limit can be walked digit by digit.
Step-by-Step Execution Trace Table
The trap case n = 190 (digits = [1, 9, 0]), at the calls where the tight bit matters. count(pos, ones, tight) returns the 1s in every number that finishes the prefix:
| Call | top | Digits tried | What happens |
|---|---|---|---|
count(0, 0, True) | 1 | 0, 1 | The first digit is 0 (numbers below 100) or 1 (100 to 190) |
count(1, 0, False) | 9 | 0..9 | After a 0 the prefix is already smaller than 190, so every second digit is free |
count(2, 0, False) | 9 | 0..9 | With tight and d == top, a 9 in the middle keeps the last digit free: 0..9 |
count(1, 1, True) | 9 | 0..9 | Still tight after the 1: the second digit may go up to 9 |
count(2, 1, True) | 0 | 0 | Tight after 1, 9: the last digit may only be 0 (the number 190) |
| End | count(0, 0, True) = 130 |
Staying tight on d == top alone would make count(2, 0, True) after the prefix 0, 9 cap the last digit at 0, dropping 91 and returning 129.
| 1 | Build every number up to `n` digit by digit from the most significant digit, and keep `tight`: whether the digits so far equal `n`'s. |
| 2 | `count(pos, ones, tight)` is the number of 1s in every number that finishes the prefix; a finished number adds its `ones`, and each allowed digit moves to `pos + 1`. |
| 3 | The shape: split `n` into its digits, a memoized count over (position, 1s so far, still tight), a base case at the end of the digits, a loop over the digits allowed at this position, and the call for position 0. |
| 4 | The trap: the next position is tight only when `tight and d == top`. `d == top` alone caps a number that was already smaller than `n`. |
Target: Number of Digit One (LeetCode 233). Every number up to `n` is written with as many digits as `n` (shorter ones get leading zeros), and the limit is checked one digit at a time.
Optimal substructure: DP state dp[i] depends strictly on already-computed subproblems. Rolling array reduces space from O(S) to O(1 tier).
Iterate base cases -> compute states in topological transition order (dp[i] = min/max/sum of transitions).
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting something over every number from 0 to n is hopeless one number at a time when n is 10^9. Digit DP builds the numbers digit by digit instead, from the most significant digit, and keeps one bit of history about the limit: tight, whether every digit so far equals n's. While tight, the next digit may not pass n's digit; once a smaller digit has been placed, every later digit is free. Add the one fact the question needs, here ones, the 1s placed so far, and the whole count is a small table over (position, ones, tight).
🔢 The Analogy: A Combination Lock With a Maximum
Think of dialling every code up to a maximum on a lock, wheel by wheel. As long as the wheels you have set match the maximum, the next wheel may only go up to the maximum's digit. The moment one wheel is set lower, the rest can spin freely from 0 to 9. You never list the codes: you count how many ways each wheel can finish.
🪄 The Mathematical Harmony / Magic Trick
@lru_cache(maxsize=None)def count(pos, ones, tight): if pos == size: return ones top = digits[pos] if tight else 9 return sum(count(pos + 1, ones + (d == 1), tight and d == top) for d in range(top + 1)) Two prefixes with the same (position, ones, tight) finish in exactly the same ways, so each state is solved once. The tight bit must pass on only when the prefix was tight and took n's digit: tight and d == top.
💡 Summary
Split the limit into digits, count over (position, the fact you need, tight), cap a digit at n's only while tight, and leave tight the moment a smaller digit is placed. About steps for a -digit n.
Staying tight on the digit alone: the next position is tight only when
tight and d == top. Usingd == topalone caps a number that was already smaller thann: after a0undern's1, a9would cap the next digit (n = 190gives 129 instead of 130).Using 9 as the top while tight:
top = digits[pos] if tight else 9. A tight prefix may not passn's digit here, or numbers abovenare counted.Counting numbers instead of 1s: the base case returns
ones, the 1s the finished number holds. Returning 1 counts the numbers, and a flag counts the numbers that contain a 1.Dropping
onesfrom the memo key:countdepends on how many 1s are already placed, so(pos, ones, tight)is the key. Caching on(pos, tight)alone reuses a total computed for a differentones.
4-Phase Thought Process Model
You will see how a senior engineer spots a count over every number up to a huge n and turns it into a walk over n's digits.
Pattern Recognition Signals
The 10-second spot
"Add up how many times the digit 1 is written across all the whole numbers from 0 to n" with n up to 10^9: a count over every number up to a limit, where the property depends only on the digits. Scanning is too slow, so walk the limit's digits: Digit DP.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
count(pos, ones, tight) is the number of 1s in every number that finishes a prefix of length pos holding ones 1s, where tight means the prefix equals n's. top = digits[pos] if tight else 9; each d in range(top + 1) moves to count(pos + 1, ones + (d == 1), tight and d == top); count(size, ones, _) = ones; the answer is count(0, 0, True).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
tight and d == top, notd == top: after a smaller digit the number is belownfor good, andd == topalone would cap it again (n = 190gives 129 instead of 130).top = digits[pos] if tight else 9: while tight the digit may not passn's, or numbers abovenare counted.The base case returns
ones, not 1: the question counts 1 digits, not numbers.The memo key is
(pos, ones, tight): caching on(pos, tight)alone reuses a total computed for a different number of 1s.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Digit DP. Scanning every number up to a billion is too slow, but the count only depends on the digits, so I build the numbers digit by digit from the front. A state is the position, how many 1s the prefix holds, and whether the prefix still equals n's, called tight. While tight, the next digit can only go up to n's digit there; otherwise it can be anything from 0 to 9. Each finished number adds its 1s. Prefixes with the same state finish the same way, so I memoize on all three. The trap is the tight bit: the next position stays tight only if this one was tight and took n's digit. Using the digit alone would cap a number that's already smaller than n. There are about D squared times two states with ten digits each, so O(D squared times 10) for D digits.
So: count(pos, ones, tight), top = digits[pos] if tight else 9, tight and d == top for the next position, a finished number adds ones.
Complexity & Mathematical Proof
O(D^2 * 10)
Look at the code: count is memoized on (pos, ones, tight). pos runs from 0 to D, ones from 0 to D and tight is True or False, so there are at most (D + 1)^2 * 2 states. Each state runs for d in range(top + 1), at most 10 digits, with O(1) work per digit. Total: O(D^2 * 10). For n up to 10^9, D is at most 10, so this is a few thousand steps.
O(D^2)
The lru_cache keeps one entry per state, O(D^2), and the recursion goes at most D + 1 calls deep. digits holds D digits. The answer is one integer.
Look at the code: count is memoized on (pos, ones, tight). pos runs from 0 to D, ones from 0 to D and tight is True or False, so there are at most (D + 1)^2 * 2 states. Each state runs for d in range(top + 1), at most 10 digits, with O(1) work per digit. Total: O(D^2 * 10). For n up to 10^9, D is at most 10, so this is a few thousand steps.
Derivation Progression
(D + 1) * (D + 1) * 2
pos from 0 to D, ones from 0 to D, and tight True or False; lru_cache solves each once.
at most 10 digits
for d in range(top + 1) tries at most 10 digits, each with one cached call and one addition.
O(D^2 * 10)
For n = 10^9, D = 10: at most 242 states and about 2,400 digit tries, against about 10^10 digit checks for the brute force.
Variable Definitions
The limit n
Number of digits of n (size in the code), at most 10
Memory Architecture & Bounds
O(D): the recursion goes one call per digit
O(D^2): the memo of (pos, ones, tight) states
O(1): one integer
Boundary Best / Worst Cases
for a one-digit n
with
State-Space & Subproblem DAG(Directed Acyclic Graph) Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: **"all the whole numbers from 0 to n"**, "how many times the digit 1 is written", with n up to . A count over every number up to a limit where the property depends only on the digits: Digit DP over (position, the fact you need, tight).
, so digits. Checking every number is about digit checks; the digit walk has at most states with up to 10 digits each. The answer is below , so a 64-bit integer is needed in fixed-width languages.
Passing d == top on instead of tight and d == top re-caps numbers that are already below n. A range [lo, hi] is two runs, f(hi) - f(lo - 1), not one walk. A property that needs more history (digits used, previous digit, a running remainder) goes into the state, and the state count is what decides whether it still fits.
Core Algorithmic State Invariants
Every number up to `n` is written with `n`'s number of digits (shorter ones get leading zeros), so counting over the numbers becomes a walk over positions from the most significant digit.
`top = digits[pos] if tight else 9`, and the next position gets `tight and d == top`. Once a smaller digit is placed the number is below `n` for good; `d == top` alone would cap it again.
`count(pos, ones, tight)` depends only on those three values, so `lru_cache` solves each of about 2D^2 states once: O(D^2 * 10) time and O(D^2) space for a D-digit `n`.
| Canonical Invariant | Concrete Code | Engineering Rationale |
|---|---|---|
| Work on the digits of the limit | digits = [int(c) for c in str(n)] | Every number up to `n` is written with as many digits as `n` (shorter ones get leading zeros), and the limit is checked one digit at a time. |
| One count per state: position, what matters so far, still tight | def count(pos: int, ones: int, tight: bool) -> int: | `tight` says the digits placed so far equal `n`'s; `ones` is the only fact about them the question needs. Every prefix with the same state finishes the same way, so `lru_cache` solves each state once. |
| A finished number | if pos == size:
return ones | It adds the 1s it holds to the total. |
| The digits allowed here | top = digits[pos] if tight else 9 | While tight the digit may not pass `n`'s digit here; once smaller, any digit goes. |
| Place each digit and move on (the trap) | total += count(pos + 1, ones + (d == 1), tight and d == top) | The next position stays tight only if this one was tight AND took `n`'s digit. `d == top` alone would cap a number that is already smaller than `n`. |
| Start at the first digit, tight | return count(0, 0, True) | An empty prefix equals the start of `n`, and it holds no 1s yet. |