Digit DP
How many numbers between 1 and have a digit sum divisible by 7? How many integers up to 321 never repeat a digit twice in a row? How many times does the digit 1 appear when you write out every number from 1 to a billion? You cannot loop over a billion billion numbers. But every one of these questions is about the digits, and a number below has at most 18 of them. Digit DP turns "look at every number" into "look at every digit position", and the work drops from astronomical to a few thousand steps.
The trick has three parts, and this lesson builds each one from scratch:
- Prefix counting. Answer "how many good numbers in ?" as , where counts good numbers in .
- The tight walk. Build numbers digit by digit, left to right. As long as your prefix equals 's prefix you are tight and must not exceed 's next digit. The moment you write a smaller digit you become free: every later digit can be anything from 0 to 9.
- Memoise the free part. Free suffixes do not care what is. They depend only on how many digits are left and a small summary of what you have written so far. That summary is the DP state.
This lesson assumes DP Foundations (state, transition, memoization vs tabulation) and is comfortable with recursion, as in Recursion & Induction. One example uses a bitmask of used digits; Bit Manipulation covers the operations.
Why this exists
Counting problems over ranges of integers show up constantly in programming contests, and they look impossible at first: the range has members, so even is out. The insight that rescues them is old and simple. Integers written in base 10 are strings over the alphabet 0–9, and "is ?" is the same as "is the digit string of lexicographically at most that of ?" (once both are padded to the same length). Many digit properties — "digit sum is divisible by ", "no two neighbours equal", "uses only the digits 1, 3, 5, 7" — can be checked by reading the digits one at a time while remembering only a little: a running remainder, the last digit, a set of used digits. In automata language, the property is recognised by a small finite automaton (a machine with finitely many states that reads one symbol at a time; see Sipser, ch. 1). Counting the strings that an automaton accepts and that are at most is a short dynamic program.
Digit DP never got a famous paper or a textbook chapter; it is competitive-programming folklore, polished through problems such as the AtCoder Educational DP Contest's S — Digit Sum and LeetCode's Number of Digit One. The same "tight prefix" decomposition, though, runs in production systems: splitting an IP range into CIDR blocks, turning numeric ranges into regular expressions, and turning range queries into a few prefix lookups in search engines (see Real-world uses).
Pattern triggers
| If the problem says or has… | Think of… |
|---|---|
| "count the integers in such that…" with up to , or more | Digit DP with |
| Bounds given as strings (" low high ") | Digit DP over the string; answer modulo |
| A property of the digits: digit sum, product, number of nonzero digits, adjacent digits, distinct digits, allowed digit set | The property is an automaton; its state becomes extra |
| "how many times does digit appear in 1..n" | Digit DP that carries a count (LeetCode 233) |
| "numbers you can write with these digits that are " | Digit DP with an allowed set and a started flag (LeetCode 902) |
| "stepping numbers", "no two adjacent equal", "no consecutive ones in binary" | extra = previous digit; base 2 for binary versions |
| "the number is divisible by " | extra = , updated as (rem * 10 + d) % m |
| "the -th smallest number with property P" | Same counts, then walk down choosing digits (unranking) |
| Leading zeros would break the property ("007" has two equal neighbours) | Add the started flag |
| A substring must (not) appear in the decimal form | extra = KMP or Aho–Corasick automaton state |
The meta-trigger: the range is far too big to scan, but each number is short, and the property can be checked left to right with a small memory. If you can write the check as a loop over the digits with a few variables, those variables are the DP state.
Intuition & first principles
Counting by hand: numbers up to 345
Let us count, by hand, the numbers in whose digit sum is divisible by 5. Write every number with exactly three digits, padding with leading zeros: 7 becomes 007, 42 becomes 042. Padding does not change a digit sum, so nothing is lost.
Now sort the numbers by their first digit:
- First digit 0, 1 or 2: the number is automatically below 345, so the last two digits can be anything from
00to99. Exactly 20 of those 100 two-digit endings make the total sum divisible by 5, whatever the first digit is. (Each digit 0–9 hits each remainder mod 5 exactly twice, so the 100 endings are spread evenly: 20 per remainder.) That is numbers. - First digit 3: we are still "on the edge". The second digit may be at most 4.
- Second digit 0, 1, 2 or 3: now we are safely below 345, and the last digit is free. For each choice exactly 2 last digits work (for
30_the sum is 3, so the last digit must be 2 or 7). That is . - Second digit 4: still on the edge, sum so far 7. The last digit may be at most 5. Digits 0–4 are safe; only 3 brings the sum to 10. That is 1.
- Last digit 5: the number 345 itself, digit sum 12. Not divisible. 0.
- Second digit 0, 1, 2 or 3: now we are safely below 345, and the last digit is free. For each choice exactly 2 last digits work (for
Total: . A program that checks all 346 numbers agrees: 69 (counting 0 itself, whose digit sum 0 is divisible by 5).
Look at the shape of that calculation. We walked down 's digits — 3, then 4, then 5 — and at each step peeled off a block of "free" numbers whose count we could look up. That walk is the whole algorithm. The digits of form one path; everything that leaves the path leaves it into a free region.
The odometer picture
Think of a car's odometer counting from 000 up to 345. The leftmost wheel is the slowest. While it shows 0, 1 or 2, the two right wheels spin through all 100 combinations. Only when the left wheel reaches 3 does the counter start to "feel" the limit: now the middle wheel stops at 4, and when it reaches 4 the right wheel stops at 5.
So the numbers break into:
- a few full sweeps of the right-hand wheels (free regions), and
- one edge path that follows exactly.
A full sweep of wheels is the same no matter which we are counting up to. If we know, for each and each "summary of the left part", how many endings of length are good, we can add up the sweeps in .
From a range to two prefixes
Most problems ask about a range , not . Use the same trick as prefix sums: let be the number of good in . Then
graph LR
A["0 .. L-1 : counted by f(L-1)"] --> B["L .. R : the answer"]
C["0 .. R : counted by f(R)"] -.->|"minus f(L-1)"| B
For and digit sum divisible by 5: . When there is nothing to subtract. When the bounds are strings, either compute as a string, or use the equivalent , which needs no subtraction at all. Both appear in the code below.
The four questions for every digit DP
- What do I need to remember about the prefix to finish checking the property? (A remainder, the last digit, a set of used digits, a count.) This is
extra. - Am I still tight? (Is my prefix equal to 's prefix?) This decides the largest digit I may write next.
- Have I started? (Have I written a nonzero digit yet, or am I still in leading zeros?) Only needed when leading zeros would change the answer.
- What counts at the end? (Accept if the remainder is 0; accept only if started; or return a count instead of 0/1.)
Mechanics
The state: (pos, tight, started, extra)
| Part | Meaning | Values |
|---|---|---|
pos | How many digits we have written (index into 's digit string) | , where = number of digits of |
tight | Is the prefix written so far exactly equal to 's prefix? | true / false |
started | Have we written a nonzero digit yet? (false = we are still inside leading zeros) | true / false |
extra | Whatever the property needs: remainder, last digit, mask of used digits, count so far… | problem-specific, size |
The transition from pos tries each digit d:
- If tight,
dranges over0 .. N[pos]; otherwise over0 .. 9. - New
tight= oldtightandd == N[pos]. Writing a smaller digit drops you off the edge forever; you can never become tight again. - New
started= oldstartedord != 0. - New
extra= the property's update rule, or "reject" if the digit breaks the property (then that branch contributes 0 and we skip it — this is pruning).
At pos == D we have written a whole number; return 1 if extra is accepting (or the count we were carrying), else 0.
graph TD
T["tight at pos i"] -->|"d equals N[i]"| T2["tight at pos i+1"]
T -->|"d less than N[i]"| F2["free at pos i+1"]
F["free at pos i"] -->|"any d from 0 to 9"| F2
Two arrows matter: a tight state has exactly one tight child, and a free state never becomes tight. So the tight states form a single path of length (one per position), and everything else hangs off it as free states.
Trace 1: the tight walk for , digit sum divisible by 5
Here extra is the digit sum modulo 5. free(r, s) = number of length- digit strings whose sum is , which is what a free branch returns. From the precomputed table, free(0, 0) = 1, free(0, s≠0) = 0, free(1, s) = 2 and free(2, s) = 20 for every .
| Step | pos | Tight prefix | Sum so far (mod 5) | Limit [pos] | Digits that leave the edge | Each needs ending sum ≡ | Free count | Running total |
|---|---|---|---|---|---|---|---|---|
| 1 | 0 | (empty) | 0 | 3 | 0, 1, 2 | 0, 4, 3 (two digits left) | 20 + 20 + 20 = 60 | 60 |
| 2 | 1 | 3 | 3 | 4 | 0, 1, 2, 3 | 2, 1, 0, 4 (one digit left) | 2 + 2 + 2 + 2 = 8 | 68 |
| 3 | 2 | 34 | 2 | 5 | 0, 1, 2, 3, 4 | sum must be 0 now | only digit 3 → 1 | 69 |
| 4 | 3 | 345 | 2 | — | — | 345 itself: sum 12, not 0 | 0 | 69 |
The program digit_sum_mod_k_up_to("345", 5) returns 69, and a brute-force loop over 0..345 gives 69 too.
Trace 2: the same count, filled forwards
The recursive view walks the edge and asks for free counts. The iterative view (used in the main implementation, because it has no recursion depth problems) pushes counts forward one digit at a time. ways[tight][s] = number of prefixes of the current length that are tight / free with digit-sum remainder s.
| After digit | Read | Tight state | Free counts by remainder [0, 1, 2, 3, 4] | Free total | Where the new free prefixes came from |
|---|---|---|---|---|---|
| start | — | sum 0 | [0, 0, 0, 0, 0] | 0 | — |
| 1 | 3 | sum 3 | [1, 1, 1, 0, 0] | 3 | tight branch wrote 0, 1, 2 |
| 2 | 4 | sum 7 ≡ 2 | [7, 7, 6, 7, 7] | 34 | 3 free × 10 digits = 30, plus tight branch wrote 0–3 → 4 more |
| 3 | 5 | sum 12 ≡ 2 | [69, 69, 69, 69, 69] | 345 | 34 × 10 = 340, plus tight branch wrote 0–4 → 5 more |
At the end, accept remainder 0: free 69 plus tight (remainder 2, rejected) 0 = 69. The free totals 3, 34, 345 are exactly the numbers of padded prefixes strictly below 3, 34 and 345 — a nice sanity check.
Why we memoise only the non-tight states
Recursive digit DP is usually written as one function go(pos, tight, started, extra) with a memo table. Two facts make the standard advice — cache only when tight is false — the right one:
- Tight states are never repeated. If
tightis true, the prefix is 's prefix, sostartedandextraare fully determined bypos. There are only tight states, and the recursion visits each exactly once. Caching them saves nothing. - A cache key without
tightis a bug. A tight state at(pos, extra)is allowed fewer digits than a free state at the same(pos, extra), so they have different answers. If you store tight results under the same key as free ones, a later lookup returns the wrong number. Doing exactly that for , returns 70 instead of 69: the tight state(pos 2, sum ≡ 2)gets the free answer 2 (last digit 3 or 8) when only digit 3 is allowed.
Either include tight in the key (correct, slightly wasteful — this is what @lru_cache on all four arguments does) or cache only free states (the classic form). Never cache tight results under a key that lacks tight.
Free states do not depend on N — only on how many digits are left
A free state's answer depends on (digits remaining, started, extra), not on . If you index the memo by digits remaining instead of pos, the same memo can serve , and many queries. If you index by pos from the left (as most code does), you must reset the memo between bounds of different lengths. Sharing a pos-indexed memo between and makes come out as 128 instead of 20, because "position 1" means two digits left for 345 but only one for 99.
Leading zeros and the started flag
Padding with zeros is harmless for digit sums. It is not harmless for many other properties:
- "No two adjacent digits are equal": the number 7, padded to
007, has two equal neighbours. Counting correctly gives 273; treating the padded strings literally gives 263 — it wrongly rejects the nine one-digit numbers 1–9 and the number 0. - "All digits distinct" (for in ): correct 110; padded strings give 92.
- "Count the zeros in 1..n": the padded
007has two zeros that do not exist. - "Numbers made only from the digits {1, 3, 5, 7}":
013contains a 0, but 13 is fine.
The fix is a boolean started = "a nonzero digit has been written". While started is false, a 0 is a leading zero: it is not a real digit, so it does not update extra (no "previous digit", no mask bit, no count). The first nonzero digit flips started to true. At the end, started == false means the number is 0 — accept or reject it as the problem wants (LeetCode 902 and 2376 count from 1, so they reject it).
Shorter numbers come for free: the number 13 inside is the string 013 with one leading zero, so "how many good numbers have fewer digits than " is handled automatically. Without started, some solutions handle shorter lengths with a separate formula; with it, one function does everything.
The template, recursively
Here is the whole technique as one reusable Python function. The property is supplied as an automaton: step(extra, d, started) returns the next extra or None to reject; accept(extra, started) decides at the end. The rest of this section instantiates it six times.
from typing import Callable, Dict, Hashable, Optional, Tuple
MOD = 10**9 + 7
State = Hashable
def digit_dp(n: str,
init: State,
step: Callable[[State, int, bool], Optional[State]],
accept: Callable[[State, bool], bool]) -> int:
"""Count x in [0, n] whose digits drive the automaton to an accepting state (mod 1e9+7).
State of the search: (pos, tight, started, extra). Only non-tight states are memoised.
"""
digits = [int(c) for c in n]
memo: Dict[Tuple[int, bool, State], int] = {}
def go(pos: int, tight: bool, started: bool, extra: State) -> int:
if pos == len(digits):
return 1 if accept(extra, started) else 0
if not tight and (pos, started, extra) in memo:
return memo[(pos, started, extra)]
limit = digits[pos] if tight else 9
total = 0
for d in range(limit + 1):
nxt = step(extra, d, started)
if nxt is None: # this digit breaks the property: prune
continue
total += go(pos + 1, tight and d == limit, started or d != 0, nxt)
total %= MOD
if not tight:
memo[(pos, started, extra)] = total
return total
return go(0, True, False, init)
The iterative version in Implementation computes the same thing without recursion, which matters when has thousands of digits.
Example 1: digit sum divisible by
extra = digit sum mod (size ). Update: (s + d) % k. Accept: s == 0. Leading zeros are harmless, so started is not needed — the template carries it anyway at the cost of a factor 2. Traced above: , and has 49.
A common twist: "the number itself is divisible by ". Then extra = of the prefix, updated as (rem * 10 + d) % m (Horner's rule). Combining both — Codeforces 55D "Beautiful numbers" asks for numbers divisible by each of their nonzero digits — needs extra = (value mod 2520, lcm of digits so far), since 2520 = lcm(1..9).
Example 2: no two adjacent digits equal
extra = the previous digit (or −1 for "none yet"). Reject when started and d == prev. While not started, a 0 leaves extra at −1, so 007 is read as just 7.
graph LR
S["none yet"] -->|"0 while not started"| S
S -->|"first nonzero d"| P["last digit = d"]
P -->|"e not equal to d"| Q["last digit = e"]
P -->|"e equals d"| X["reject"]
The CSES problem "Counting Numbers" uses exactly this property. For : , matching a brute-force count.
Example 3: how many times does digit appear in 1..n (LeetCode 233)
Now we count occurrences, not numbers. The cleanest trick: carry cnt = how many 's the prefix contains, and at the end return cnt instead of 1. The recursion then sums cnt over every number, which is exactly the total number of occurrences.
Small trace for , (digits 1 3):
| Branch | Numbers covered | Ones in each | Contribution |
|---|---|---|---|
| first digit 0 (free, not started) | 0–9 (as 00–09) | only 01 has a one | 1 |
| first digit 1 (tight), second 0 | 10 | 1 | 1 |
| first digit 1, second 1 | 11 | 2 | 2 |
| first digit 1, second 2 | 12 | 1 | 1 |
| first digit 1, second 3 (still tight) | 13 | 1 | 1 |
| total | 6 |
cnt ranges over , so the state space is — tiny. For the started flag is essential (leading zeros are not zeros). The Implementation section has this in four languages, checked against brute force for every digit 0–9 and every ; for the answer is 900,000,001.
An alternative that avoids the extra dimension: let each state return a pair (how many numbers, how many 's in total). Appending digit to a set of numbers adds occurrences. This "carry (count, sum) together" idea is how digit DP computes sums of digit sums, sums of the numbers themselves, and so on.
Example 4: all digits distinct (LeetCode 2376 Count Special Integers)
extra = a 10-bit mask of digits used so far (bit set means digit appeared). Reject if bit d is already set. Leading zeros must not set bit 0, otherwise 10, 20, … would look like they repeat the zero. Accept only if started (the problem counts from 1).
State space: , with 10 digits per state: about steps for . LeetCode's examples: (only 11 repeats), , . LeetCode 1012 "Numbers With Repeated Digits" is the complement: (this count).
Example 5: numbers made only of given digits (LeetCode 902)
extra is trivial (one state); the property is just "every real digit is in the allowed set". A leading zero is allowed (it means "a shorter number") even if 0 is not in the set. Accept only if started. With digits {1, 3, 5, 7} and : the 4 one-digit numbers plus two-digit ones, total 20. With {1, 4, 9} and : (the 10-digit number would have to be at most 1000000000, and none of its digits may be 0). With {7} and : 1.
Example 6: stepping numbers, bounds as strings (LeetCode 2801)
A stepping number has neighbouring digits that differ by exactly 1: 1, 10, 12, 21, 23, 98, 101, 121, … LeetCode 2801 gives low and high as strings of up to 100 digits and wants the count modulo .
extra = previous digit (−1 before starting). Reject when started and |prev − d| ≠ 1. Accept only if started (0 is excluded because the range starts at 1).
Examples: (1–9 and 10); (98 and 101). For the count is 125,046,265 mod ; an independent method (counting walks on the path graph 0–1–…–9, length by length) gives the same value.
Handling huge bounds given as strings
When has hundreds or thousands of digits:
- Read as a string, never parse it into an integer type (Python can, but Java's
longand JavaScript'snumbercannot). - Do every addition modulo and remember that a modular subtraction can go negative:
((a - b) % MOD + MOD) % MODin Java, C++ and TypeScript. - For either decrement the string (borrow through trailing zeros:
"1000" → "999", then strip leading zeros) or compute , checking directly by looping over its digits. - Prefer the iterative (forward) DP or raise the recursion limit: a 10,000-digit bound means a recursion depth of 10,000.
The six examples above, using the template:
def decrement(s: str) -> str:
"""Decimal string minus one, for s >= "1". "1000" -> "999", "1" -> "0"."""
digits = list(s)
i = len(digits) - 1
while digits[i] == "0": # borrow through trailing zeros
digits[i] = "9"
i -= 1
digits[i] = str(int(digits[i]) - 1)
out = "".join(digits).lstrip("0")
return out or "0"
def count_range(lo: str, hi: str, f) -> int:
"""f(hi) - f(lo - 1), where f(n) counts good x in [0, n]."""
below = f(decrement(lo)) if lo != "0" else 0
return (f(hi) - below) % MOD
# 1. digit sum divisible by k
def digit_sum_div(n: str, k: int) -> int:
return digit_dp(n, 0, lambda s, d, st: (s + d) % k, lambda s, st: s == 0)
# 2. no two adjacent digits equal (CSES 2220 Counting Numbers)
def no_equal_adjacent(n: str) -> int:
def step(prev, d, started):
if started and d == prev:
return None
return d if (started or d != 0) else -1 # -1 = "no previous digit yet"
return digit_dp(n, -1, step, lambda s, st: True)
# 3. all digits distinct, x in [1, n] (LeetCode 2376 Count Special Integers)
def count_special(n: int) -> int:
def step(mask, d, started):
if not started and d == 0:
return mask # still a leading zero: uses nothing
if mask >> d & 1:
return None
return mask | (1 << d)
return digit_dp(str(n), 0, step, lambda m, st: st) # st: exclude x = 0
# 4. numbers in [1, n] written only with the allowed digits (LeetCode 902)
def at_most_n_given_digit_set(allowed: list, n: int) -> int:
ok = {int(c) for c in allowed}
def step(s, d, started):
if not started and d == 0:
return 0 # leading zero: "shorter number"
return 0 if d in ok else None
return digit_dp(str(n), 0, step, lambda s, st: st)
# 5. stepping numbers in [low, high], bounds as strings (LeetCode 2801)
def count_stepping_numbers(low: str, high: str) -> int:
def step(prev, d, started):
if not started:
return d if d != 0 else -1
return d if abs(prev - d) == 1 else None
f = lambda n: digit_dp(n, -1, step, lambda s, st: st)
return count_range(low, high, f)
if __name__ == "__main__":
assert decrement("1000") == "999" and decrement("1") == "0" and decrement("120") == "119"
assert digit_sum_div("345", 5) == 69
assert count_range("100", "345", lambda n: digit_sum_div(n, 5)) == 49
assert count_range("123", "321", no_equal_adjacent) == 171
assert no_equal_adjacent("321") == 273
assert [count_special(n) for n in (20, 5, 135)] == [19, 5, 110]
assert at_most_n_given_digit_set(["1", "3", "5", "7"], 100) == 20
assert at_most_n_given_digit_set(["1", "4", "9"], 10**9) == 29523
assert at_most_n_given_digit_set(["7"], 8) == 1
assert count_stepping_numbers("1", "11") == 10
assert count_stepping_numbers("90", "101") == 2
# brute force on small ranges
adj = lambda s: all(a != b for a, b in zip(s, s[1:]))
step_ok = lambda s: all(abs(int(a) - int(b)) == 1 for a, b in zip(s, s[1:]))
for n in range(0, 2500):
s = str(n)
assert no_equal_adjacent(s) == sum(adj(str(x)) for x in range(n + 1))
assert count_special(n) == sum(len(set(str(x))) == len(str(x)) for x in range(1, n + 1))
assert at_most_n_given_digit_set(["0", "2", "9"], n) == sum(
set(str(x)) <= {"0", "2", "9"} for x in range(1, n + 1))
for lo in range(1, 400, 13):
for hi in range(lo, 1200, 41):
assert count_stepping_numbers(str(lo), str(hi)) == sum(
step_ok(str(x)) for x in range(lo, hi + 1))
print(count_stepping_numbers("1", "9" * 100))
print("all example tests passed")
The ladder: brute force → better → optimal
Problem: count whose digit sum is divisible by .
Rung 1: check every number
def count_brute(lo: int, hi: int, k: int) -> int:
"""Digit sum divisible by k, by looking at every number. O((hi - lo) * digits)."""
return sum(1 for x in range(lo, hi + 1) if sum(map(int, str(x))) % k == 0)
assert count_brute(100, 345, 5) == 49
Time . Perfect for , hopeless for ( numbers at per second is 30 years). Keep it — it is the oracle every digit DP should be tested against.
Rung 2: recurse over digits, no memo
Generating numbers digit by digit with the tight flag is correct but, without a memo, it still visits every number once — the recursion tree's leaves are the numbers.
def count_no_memo(n: str, k: int) -> int:
"""Walk every digit string <= n. Correct, but visits all n + 1 numbers."""
def go(pos: int, rem: int, tight: bool) -> int:
if pos == len(n):
return 1 if rem == 0 else 0
limit = int(n[pos]) if tight else 9
return sum(go(pos + 1, (rem + d) % k, tight and d == limit) for d in range(limit + 1))
return go(0, 0, True)
assert count_no_memo("345", 5) == 69
Time . No better than rung 1, but it already has the right shape: the only thing missing is noticing that the free subtrees repeat.
Rung 3: memoise the free states (digit DP)
Add a memo on (pos, rem) for free states. Each free state is solved once; there are of them, each trying 10 digits. Time per bound, memory . For and : about steps, instead of .
Rung 4: precompute once, answer many queries
Index the free table by digits remaining and build it once: free[r][s] for . Each query then only walks its tight path, . With queries this is the difference between rebuilding a table each time and a few hundred operations per query. For some properties the free table even has a closed form: for LeetCode 233, the count of ones has a per-position formula (below) that runs in .
def count_digit_one_formula(n: int) -> int:
total, p = 0, 1
while p <= n:
high, cur, low = n // (p * 10), (n // p) % 10, n % p
total += high * p
if cur > 1:
total += p
elif cur == 1:
total += low + 1
p *= 10
return total
run = 0
for n in range(1, 5000):
run += str(n).count("1")
assert count_digit_one_formula(n) == run
assert count_digit_one_formula(13) == 6 and count_digit_one_formula(0) == 0
| Rung | Method | Time | Extra space | Why it is better than the rung above |
|---|---|---|---|---|
| 1 | Check every number | Baseline; obviously correct; the test oracle | ||
| 2 | Digit recursion, no memo | in total work | stack | Same speed, but the structure (tight flag, digits) is now explicit |
| 3 | Digit DP, memo on free states | per bound | Each free subtree computed once instead of once per number in it | |
| 4 | Shared free table / closed form | once, then per query | Many queries share the free table |
Here is the number of digits (19 for ) and the number of extra values (×2 if started matters).
Correctness
Claim 1 (prefix counting). For , the good numbers in number , with . The good numbers in split into those in and those in , disjointly. Equivalently .
Claim 2 (padding is a bijection). Padding each with leading zeros to exactly digits is a one-to-one map onto the -digit strings that are lexicographically the string of . (For equal-length digit strings, numeric order and lexicographic order agree.) So counting numbers is counting strings — provided the property is evaluated on the unpadded number, which is what the started flag guarantees.
Claim 3 (the partition by first difference). Every string of length is either itself, or there is a unique first position where , and then . So the strings split into disjoint classes : "agree with on positions , have digit at position , anything after". This is exactly the tight walk: the tight path visits positions , and at position it branches into free states for each . Every number is counted once (Trace 1 adds up the classes for 345).
Claim 4 (free counts depend only on the state). Inside class the last digits range over all of . Whether the full string is good depends only on the automaton state after the prefix (that is what "the property is an automaton" means: the future of the check depends on the past only through extra and started). So the number of good completions is a function of (digits left, started, extra) — the memoised value. Formally, by induction on digits left : , and (skipping rejected digits), because the first digit of the completion is one of 0..9 and the rest is any good completion from the new state.
Claim 5 (why the memo key is safe). A free state's answer is free from Claim 4, which does not mention 's digits. A tight state's answer does depend on 's remaining digits, which is why it must not share a key with a free state (the 70-vs-69 bug), and why a pos-indexed memo cannot be reused across bounds of different lengths (the 128-vs-20 bug).
Together: , which is what both the recursive and iterative implementations compute.
LeetCode 233 (counting occurrences). Returning cnt at the leaves makes each state return . By the same partition, the root returns the sum over all . cnt is part of the key, so memoised values are again functions of the state alone.
Complexity
Let = number of digits of (), = number of extra values, = base (10).
| Problem | extra | States | Time | Space |
|---|---|---|---|---|
| Digit sum mod | remainder, | , or iteratively | ||
| Digit sum in (LeetCode 2719) | sum, | |||
| No two adjacent equal | previous digit, | |||
| Count of digit (LeetCode 233) | count, | |||
| Distinct digits (LeetCode 2376) | mask, | |||
| Allowed digit set (LeetCode 902) | none, | |||
| Stepping numbers (LeetCode 2801) | previous digit, | |||
| Number divisible by | value mod |
Plus the tight path: , negligible. A range query runs the DP twice. The answer is logarithmic in — for , — which is why digit DP handles bounds that are themselves 10,000 digits long (AtCoder DP S) in well under a second.
There is no meaningful best/average/worst split: the work is fixed by and . Memoised recursion may touch fewer states than the full table (only reachable ones); the iterative version touches all of them but has no recursion overhead.
Number sizes. Counts up to fit in 64 bits when . Occurrence counts can exceed (LeetCode 233 with gives 900,000,001, about ); for near that would be about , still under , but sums of numbers or sums of digit sums overflow — use a modulus or big integers. With string bounds, everything is modulo .
Implementation
Generic digit-DP template (digit sum mod , bounds as strings)
The template is iterative and works for any automaton: pass the number of states, the start state, step (return −1 / None to reject) and accept. ways[tight][started][state] is pushed forward one digit at a time. It is instantiated with "digit sum divisible by " and handles bounds with thousands of digits. Every snippet checks itself against brute force on small ranges and against the three published samples of AtCoder DP Contest S (which counts , so it subtracts the number 0).
from typing import Callable, Optional
MOD = 10**9 + 7
def count_up_to(n: str, num_states: int, init: int,
step: Callable[[int, int, bool], Optional[int]],
accept: Callable[[int, bool], bool]) -> int:
"""Count x in [0, n] (n is a decimal string) whose digit string the automaton accepts.
step(state, digit, started) -> next state, or None to reject.
started is False while we are still inside leading zeros.
"""
# ways[tight][started][state]; tight=1 means "prefix equals n's prefix so far"
ways = [[[0] * num_states for _ in range(2)] for _ in range(2)]
ways[1][0][init] = 1
for ch in n:
limit = int(ch)
nxt = [[[0] * num_states for _ in range(2)] for _ in range(2)]
for tight in (0, 1):
for started in (0, 1):
for s in range(num_states):
w = ways[tight][started][s]
if w == 0:
continue
top = limit if tight else 9
for d in range(top + 1):
ns = step(s, d, bool(started))
if ns is None:
continue
nt = 1 if (tight and d == limit) else 0
nst = 1 if (started or d != 0) else 0
nxt[nt][nst][ns] = (nxt[nt][nst][ns] + w) % MOD
ways = nxt
total = 0
for tight in (0, 1):
for started in (0, 1):
for s in range(num_states):
if accept(s, bool(started)):
total = (total + ways[tight][started][s]) % MOD
return total
def digit_sum_mod_k_up_to(n: str, k: int) -> int:
"""How many x in [0, n] have digit sum divisible by k (mod 1e9+7)."""
return count_up_to(n, k, 0, lambda s, d, started: (s + d) % k,
lambda s, started: s == 0)
def digit_sum_mod_k_in_range(lo: str, hi: str, k: int) -> int:
"""How many x in [lo, hi] have digit sum divisible by k. f(hi) - f(lo) + [lo itself]."""
lo_ok = 1 if sum(map(int, lo)) % k == 0 else 0
return (digit_sum_mod_k_up_to(hi, k) - digit_sum_mod_k_up_to(lo, k) + lo_ok) % MOD
if __name__ == "__main__":
assert digit_sum_mod_k_up_to("345", 5) == 69 # includes x = 0
assert digit_sum_mod_k_in_range("100", "345", 5) == 49
for k in (1, 2, 3, 5, 7): # brute force on small ranges
for lo in range(0, 120, 11):
for hi in range(lo, 400, 37):
want = sum(1 for x in range(lo, hi + 1) if sum(map(int, str(x))) % k == 0)
assert digit_sum_mod_k_in_range(str(lo), str(hi), k) == want
# AtCoder DP Contest S counts 1..K, so subtract x = 0
assert (digit_sum_mod_k_up_to("30", 4) - 1) % MOD == 6
assert (digit_sum_mod_k_up_to("1000000009", 1) - 1) % MOD == 2
assert (digit_sum_mod_k_up_to("98765432109876543210", 58) - 1) % MOD == 635270834
big = "9" * 2000 # a 2000-digit bound is no problem
print(digit_sum_mod_k_up_to(big, 7))
print("digit-sum template tests passed")
public class DigitDP {
static final long MOD = 1_000_000_007L;
interface Step { int next(int state, int digit, boolean started); } // -1 = reject
interface Accept { boolean ok(int state, boolean started); }
/** Count x in [0, n] (n a decimal string) accepted by the digit automaton, mod 1e9+7. */
static long countUpTo(String n, int numStates, int init, Step step, Accept accept) {
long[][][] ways = new long[2][2][numStates]; // [tight][started][state]
ways[1][0][init] = 1;
for (int i = 0; i < n.length(); i++) {
int limit = n.charAt(i) - '0';
long[][][] nxt = new long[2][2][numStates];
for (int tight = 0; tight < 2; tight++)
for (int started = 0; started < 2; started++)
for (int s = 0; s < numStates; s++) {
long w = ways[tight][started][s];
if (w == 0) continue;
int top = tight == 1 ? limit : 9;
for (int d = 0; d <= top; d++) {
int ns = step.next(s, d, started == 1);
if (ns < 0) continue;
int nt = (tight == 1 && d == limit) ? 1 : 0;
int nst = (started == 1 || d != 0) ? 1 : 0;
nxt[nt][nst][ns] = (nxt[nt][nst][ns] + w) % MOD;
}
}
ways = nxt;
}
long total = 0;
for (int tight = 0; tight < 2; tight++)
for (int started = 0; started < 2; started++)
for (int s = 0; s < numStates; s++)
if (accept.ok(s, started == 1)) total = (total + ways[tight][started][s]) % MOD;
return total;
}
static long digitSumModKUpTo(String n, int k) {
return countUpTo(n, k, 0, (s, d, started) -> (s + d) % k, (s, started) -> s == 0);
}
static long digitSumModKInRange(String lo, String hi, int k) {
int sum = 0;
for (char c : lo.toCharArray()) sum += c - '0';
long loOk = sum % k == 0 ? 1 : 0;
return ((digitSumModKUpTo(hi, k) - digitSumModKUpTo(lo, k) + loOk) % MOD + MOD) % MOD;
}
static int digitSum(int x) { int s = 0; for (; x > 0; x /= 10) s += x % 10; return s; }
public static void main(String[] args) {
check(digitSumModKUpTo("345", 5) == 69);
check(digitSumModKInRange("100", "345", 5) == 49);
for (int k : new int[]{1, 2, 3, 5, 7})
for (int lo = 0; lo < 120; lo += 11)
for (int hi = lo; hi < 400; hi += 37) {
long want = 0;
for (int x = lo; x <= hi; x++) if (digitSum(x) % k == 0) want++;
check(digitSumModKInRange(String.valueOf(lo), String.valueOf(hi), k) == want);
}
check((digitSumModKUpTo("30", 4) - 1 + MOD) % MOD == 6);
check((digitSumModKUpTo("1000000009", 1) - 1 + MOD) % MOD == 2);
check((digitSumModKUpTo("98765432109876543210", 58) - 1 + MOD) % MOD == 635270834);
check(digitSumModKUpTo("9".repeat(2000), 7) == 117625895);
System.out.println("digit-sum template tests passed");
}
static void check(boolean ok) { if (!ok) throw new AssertionError("test failed"); }
}
#include <cassert>
#include <functional>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const long long MOD = 1'000'000'007LL;
// Count x in [0, n] (n a decimal string) accepted by the digit automaton, mod 1e9+7.
// step(state, digit, started) returns the next state, or -1 to reject.
long long countUpTo(const string& n, int numStates, int init,
const function<int(int, int, bool)>& step,
const function<bool(int, bool)>& accept) {
// ways[tight][started][state]
vector<vector<vector<long long>>> ways(2, vector<vector<long long>>(2, vector<long long>(numStates, 0)));
ways[1][0][init] = 1;
for (char ch : n) {
int limit = ch - '0';
vector<vector<vector<long long>>> nxt(2, vector<vector<long long>>(2, vector<long long>(numStates, 0)));
for (int tight = 0; tight < 2; tight++)
for (int started = 0; started < 2; started++)
for (int s = 0; s < numStates; s++) {
long long w = ways[tight][started][s];
if (w == 0) continue;
int top = tight ? limit : 9;
for (int d = 0; d <= top; d++) {
int ns = step(s, d, started == 1);
if (ns < 0) continue;
int nt = (tight && d == limit) ? 1 : 0;
int nst = (started || d != 0) ? 1 : 0;
nxt[nt][nst][ns] = (nxt[nt][nst][ns] + w) % MOD;
}
}
ways = nxt;
}
long long total = 0;
for (int tight = 0; tight < 2; tight++)
for (int started = 0; started < 2; started++)
for (int s = 0; s < numStates; s++)
if (accept(s, started == 1)) total = (total + ways[tight][started][s]) % MOD;
return total;
}
long long digitSumModKUpTo(const string& n, int k) {
return countUpTo(n, k, 0, [k](int s, int d, bool) { return (s + d) % k; },
[](int s, bool) { return s == 0; });
}
long long digitSumModKInRange(const string& lo, const string& hi, int k) {
int sum = 0;
for (char c : lo) sum += c - '0';
long long loOk = sum % k == 0 ? 1 : 0;
return ((digitSumModKUpTo(hi, k) - digitSumModKUpTo(lo, k) + loOk) % MOD + MOD) % MOD;
}
int digitSum(int x) { int s = 0; for (; x > 0; x /= 10) s += x % 10; return s; }
int main() {
assert(digitSumModKUpTo("345", 5) == 69);
assert(digitSumModKInRange("100", "345", 5) == 49);
for (int k : {1, 2, 3, 5, 7})
for (int lo = 0; lo < 120; lo += 11)
for (int hi = lo; hi < 400; hi += 37) {
long long want = 0;
for (int x = lo; x <= hi; x++) if (digitSum(x) % k == 0) want++;
assert(digitSumModKInRange(to_string(lo), to_string(hi), k) == want);
}
assert((digitSumModKUpTo("30", 4) - 1 + MOD) % MOD == 6);
assert((digitSumModKUpTo("1000000009", 1) - 1 + MOD) % MOD == 2);
assert((digitSumModKUpTo("98765432109876543210", 58) - 1 + MOD) % MOD == 635270834);
assert(digitSumModKUpTo(string(2000, '9'), 7) == 117625895);
cout << "digit-sum template tests passed\n";
return 0;
}
const MOD = 1_000_000_007n;
type Step = (state: number, digit: number, started: boolean) => number; // -1 = reject
type Accept = (state: number, started: boolean) => boolean;
// Count x in [0, n] (n a decimal string) accepted by the digit automaton, mod 1e9+7.
// Counts are kept as bigint so the modular sums stay exact.
function countUpTo(n: string, numStates: number, init: number, step: Step, accept: Accept): bigint {
const fresh = (): bigint[][][] =>
[0, 1].map(() => [0, 1].map(() => new Array<bigint>(numStates).fill(0n)));
let ways = fresh(); // ways[tight][started][state]
ways[1][0][init] = 1n;
for (const ch of n) {
const limit = ch.charCodeAt(0) - 48;
const nxt = fresh();
for (let tight = 0; tight < 2; tight++)
for (let started = 0; started < 2; started++)
for (let s = 0; s < numStates; s++) {
const w = ways[tight][started][s];
if (w === 0n) continue;
const top = tight ? limit : 9;
for (let d = 0; d <= top; d++) {
const ns = step(s, d, started === 1);
if (ns < 0) continue;
const nt = tight && d === limit ? 1 : 0;
const nst = started || d !== 0 ? 1 : 0;
nxt[nt][nst][ns] = (nxt[nt][nst][ns] + w) % MOD;
}
}
ways = nxt;
}
let total = 0n;
for (let tight = 0; tight < 2; tight++)
for (let started = 0; started < 2; started++)
for (let s = 0; s < numStates; s++)
if (accept(s, started === 1)) total = (total + ways[tight][started][s]) % MOD;
return total;
}
function digitSumModKUpTo(n: string, k: number): bigint {
return countUpTo(n, k, 0, (s, d) => (s + d) % k, (s) => s === 0);
}
function digitSumModKInRange(lo: string, hi: string, k: number): bigint {
let sum = 0;
for (const c of lo) sum += c.charCodeAt(0) - 48;
const loOk = sum % k === 0 ? 1n : 0n;
return (((digitSumModKUpTo(hi, k) - digitSumModKUpTo(lo, k) + loOk) % MOD) + MOD) % MOD;
}
function assert(ok: boolean, msg = "test failed"): void {
if (!ok) throw new Error(msg);
}
const digitSum = (x: number): number => [...String(x)].reduce((a, c) => a + Number(c), 0);
assert(digitSumModKUpTo("345", 5) === 69n);
assert(digitSumModKInRange("100", "345", 5) === 49n);
for (const k of [1, 2, 3, 5, 7])
for (let lo = 0; lo < 120; lo += 11)
for (let hi = lo; hi < 400; hi += 37) {
let want = 0n;
for (let x = lo; x <= hi; x++) if (digitSum(x) % k === 0) want++;
assert(digitSumModKInRange(String(lo), String(hi), k) === want);
}
assert((digitSumModKUpTo("30", 4) - 1n + MOD) % MOD === 6n);
assert((digitSumModKUpTo("1000000009", 1) - 1n + MOD) % MOD === 2n);
assert((digitSumModKUpTo("98765432109876543210", 58) - 1n + MOD) % MOD === 635270834n);
assert(digitSumModKUpTo("9".repeat(2000), 7) === 117625895n);
console.log("digit-sum template tests passed");
The TypeScript version keeps counts as bigint: the sum of two values below fits in a number, but this keeps the code safe if you later multiply counts (for example when combining two DPs). std::function in C++ costs an indirect call per transition; for speed-critical code, make countUpTo a template over the lambda types.
LeetCode 233: occurrences of a digit, recursive with a non-tight memo
This is the classic recursive form: one function go(pos, cnt, tight, started), memo consulted and filled only when tight is false. countDigit(n, d) works for every digit, including 0 (thanks to started).
from typing import Dict, Tuple
def count_digit(n: int, d: int) -> int:
"""Total occurrences of digit d in the decimal forms of 1, 2, ..., n."""
if n <= 0:
return 0
digits = list(map(int, str(n)))
memo: Dict[Tuple[int, int, bool], int] = {} # non-tight states only
def go(pos: int, cnt: int, tight: bool, started: bool) -> int:
if pos == len(digits):
return cnt # this number contributes cnt copies of d
if not tight and (pos, cnt, started) in memo:
return memo[(pos, cnt, started)]
top = digits[pos] if tight else 9
total = 0
for x in range(top + 1):
ns = started or x != 0 # leading zeros are not real digits
nc = cnt + (1 if (x == d and ns) else 0)
total += go(pos + 1, nc, tight and x == top, ns)
if not tight: # tight states lie on one path: never reused
memo[(pos, cnt, started)] = total
return total
return go(0, 0, True, False)
def count_digit_one(n: int) -> int:
"""LeetCode 233: number of digit 1s in all integers from 0 to n."""
return count_digit(n, 1)
if __name__ == "__main__":
assert count_digit_one(13) == 6 # 1, 10, 11 (two), 12, 13
assert count_digit_one(0) == 0
assert count_digit_one(99) == 20
assert count_digit_one(345) == 175
assert count_digit_one(10**9) == 900000001
for d in range(10): # brute force for every digit, n < 1500
running = 0
for n in range(1, 1500):
running += str(n).count(str(d))
assert count_digit(n, d) == running
print("LeetCode 233 tests passed")
import java.util.Arrays;
public class CountDigitOne {
private int[] digits;
private int target;
private long[][][] memo; // memo[pos][cnt][started], non-tight states only
/** Total occurrences of digit d in 1, 2, ..., n. */
long countDigit(long n, int d) {
if (n <= 0) return 0;
String s = Long.toString(n);
digits = new int[s.length()];
for (int i = 0; i < s.length(); i++) digits[i] = s.charAt(i) - '0';
target = d;
memo = new long[digits.length + 1][digits.length + 1][2];
for (long[][] a : memo) for (long[] b : a) Arrays.fill(b, -1);
return go(0, 0, true, false);
}
private long go(int pos, int cnt, boolean tight, boolean started) {
if (pos == digits.length) return cnt;
int st = started ? 1 : 0;
if (!tight && memo[pos][cnt][st] >= 0) return memo[pos][cnt][st];
int top = tight ? digits[pos] : 9;
long total = 0;
for (int x = 0; x <= top; x++) {
boolean ns = started || x != 0;
int nc = cnt + ((x == target && ns) ? 1 : 0);
total += go(pos + 1, nc, tight && x == top, ns);
}
if (!tight) memo[pos][cnt][st] = total; // tight states are on a single path: skip
return total;
}
/** LeetCode 233. */
public int countDigitOne(int n) { return (int) countDigit(n, 1); }
public static void main(String[] args) {
CountDigitOne sol = new CountDigitOne();
check(sol.countDigitOne(13) == 6);
check(sol.countDigitOne(0) == 0);
check(sol.countDigitOne(99) == 20);
check(sol.countDigitOne(345) == 175);
check(sol.countDigit(1_000_000_000L, 1) == 900_000_001L);
for (int d = 0; d < 10; d++) {
long running = 0;
for (int n = 1; n < 1500; n++) {
for (int x = n; x > 0; x /= 10) if (x % 10 == d) running++;
check(sol.countDigit(n, d) == running);
}
}
System.out.println("LeetCode 233 tests passed");
}
static void check(boolean ok) { if (!ok) throw new AssertionError("test failed"); }
}
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
class CountDigitOne {
vector<int> digits;
int target = 1;
vector<vector<vector<long long>>> memo; // memo[pos][cnt][started], non-tight only
long long go(int pos, int cnt, bool tight, bool started) {
if (pos == (int)digits.size()) return cnt;
if (!tight && memo[pos][cnt][started] >= 0) return memo[pos][cnt][started];
int top = tight ? digits[pos] : 9;
long long total = 0;
for (int x = 0; x <= top; x++) {
bool ns = started || x != 0; // leading zeros are not real digits
int nc = cnt + ((x == target && ns) ? 1 : 0);
total += go(pos + 1, nc, tight && x == top, ns);
}
if (!tight) memo[pos][cnt][started] = total; // tight states are never reused
return total;
}
public:
// Total occurrences of digit d in 1, 2, ..., n.
long long countDigit(long long n, int d) {
if (n <= 0) return 0;
string s = to_string(n);
digits.assign(s.size(), 0);
for (size_t i = 0; i < s.size(); i++) digits[i] = s[i] - '0';
target = d;
int L = s.size();
memo.assign(L + 1, vector<vector<long long>>(L + 1, vector<long long>(2, -1)));
return go(0, 0, true, false);
}
int countDigitOne(int n) { return (int)countDigit(n, 1); } // LeetCode 233
};
int main() {
CountDigitOne sol;
assert(sol.countDigitOne(13) == 6);
assert(sol.countDigitOne(0) == 0);
assert(sol.countDigitOne(99) == 20);
assert(sol.countDigitOne(345) == 175);
assert(sol.countDigit(1000000000LL, 1) == 900000001LL);
for (int d = 0; d < 10; d++) {
long long running = 0;
for (int n = 1; n < 1500; n++) {
for (int x = n; x > 0; x /= 10) if (x % 10 == d) running++;
assert(sol.countDigit(n, d) == running);
}
}
cout << "LeetCode 233 tests passed\n";
return 0;
}
// Total occurrences of digit d in 1, 2, ..., n (n up to about 1e15 stays exact in a number).
function countDigit(n: number, d: number): number {
if (n <= 0) return 0;
const digits = [...String(n)].map(Number);
const memo = new Map<string, number>(); // non-tight states only
const go = (pos: number, cnt: number, tight: boolean, started: boolean): number => {
if (pos === digits.length) return cnt;
const key = `${pos},${cnt},${started ? 1 : 0}`;
if (!tight && memo.has(key)) return memo.get(key)!;
const top = tight ? digits[pos] : 9;
let total = 0;
for (let x = 0; x <= top; x++) {
const ns = started || x !== 0; // leading zeros are not real digits
const nc = cnt + (x === d && ns ? 1 : 0);
total += go(pos + 1, nc, tight && x === top, ns);
}
if (!tight) memo.set(key, total); // tight states are never reused
return total;
};
return go(0, 0, true, false);
}
// LeetCode 233
function countDigitOne(n: number): number {
return countDigit(n, 1);
}
function assert(ok: boolean, msg = "test failed"): void {
if (!ok) throw new Error(msg);
}
assert(countDigitOne(13) === 6);
assert(countDigitOne(0) === 0);
assert(countDigitOne(99) === 20);
assert(countDigitOne(345) === 175);
assert(countDigitOne(1_000_000_000) === 900_000_001);
for (let d = 0; d < 10; d++) {
let running = 0;
for (let n = 1; n < 1500; n++) {
for (let x = n; x > 0; x = Math.floor(x / 10)) if (x % 10 === d) running++;
assert(countDigit(n, d) === running);
}
}
console.log("LeetCode 233 tests passed");
All eight snippets were extracted from this page and run (Python 3.12, JDK 21, g++ C++17, Node 24); every assertion passes.
Real-world uses
Digit DP itself is mostly a contest and interview technique. Its core move — split a range into a tight path plus aligned free blocks — is used in real systems:
- IP ranges to CIDR blocks. A range of IPv4 addresses such as 10.0.0.5–10.0.0.20 is stored in routing tables and firewalls as a list of prefix blocks (
10.0.0.5/32,10.0.0.6/31,10.0.0.8/29,10.0.0.16/30,10.0.0.20/32). Each block is a "free suffix" of bits under a fixed prefix — the same decomposition as the tight walk, in base 2. Python exposes it asipaddress.summarize_address_range. - Numeric ranges as regular expressions. The npm package
to-regex-range(used by the micromatch/braces glob libraries for patterns like{1..100}) turns a range such as 1–100 into a regex like[1-9]|[1-9][0-9]|100. Each alternative is "a fixed prefix, then any digits" — the free blocks of a digit DP. - Numeric range queries in search engines. Lucene 2.9 introduced trie-encoded numeric fields and
NumericRangeQuery, which indexed each number at several precisions and answered a range query by splitting it into a small number of prefix-aligned sub-ranges, much like walking both bounds' digits. (Lucene 6 later replaced this with BKD-tree "points", so this is a historical example.) - Ranking and unranking. "Which is the 1,000,000th number with distinct digits?" uses the same counts: at each position, try digits in order and subtract the size of each free block until the target falls inside one. Combinatorial generators and some ID schemes use this to jump straight to the -th valid code without enumerating.
- Automata and model counting. Counting the strings of a regular language with length or lexicographically a bound is digit DP over the product of two automata (the property's and ""). Constraint solvers and string-analysis tools that count solutions use this construction (see Sipser for the product construction).
- Check-digit schemes (illustrative). "How many card numbers in a block pass the Luhn checksum?" — Luhn is a small automaton over digits (running sum mod 10 plus position parity), so it is a textbook digit DP; in practice the answer is "about one in ten", but the DP gives exact counts for odd-shaped ranges.
Pitfalls & edge cases
- Caching tight states under a key without
tight. Gives wrong answers (70 instead of 69 in the running example). Cache only free states, or includetightin the key. - Reusing a
pos-indexed memo across different bounds. then with a shared memo returns 128 for . Reset the memo per bound, or index by digits remaining. - Leading zeros. Properties about adjacent digits, distinct digits, digit counts, or allowed digit sets need
started. Test with one-digit and two-digit bounds — that is where the bug shows. - or . with means ; do not call the DP on "-1". Decrementing the string "1" gives "0", which is fine.
- Whether 0 counts. naturally counts (all leading zeros). Many problems start at 1: subtract 1 if 0 is good, or accept only when
started. - Negative modular differences. taken mod can be negative in Java, C++ and TypeScript. Add before the final
%. - Parsing a 100-digit bound into a 64-bit integer. Keep it as a string.
- Recursion depth. A recursive digit DP on a 10,000-digit bound overflows Python's default limit (1000) and may overflow a JavaScript stack. Use the iterative version.
- Mixing up "digit sum divisible by " and "number divisible by ". The first updates
(s + d) % k, the second(r * 10 + d) % k. For or they coincide, which hides the bug in small tests; test with . - Forgetting the bound itself. In the forward DP, the tight state at the end is the number ; it must be included if it is good.
- Pruning too early. Rejecting a branch when a running sum exceeds a maximum is fine (sums only grow). Rejecting when it is below a minimum is wrong (later digits can raise it).
Variations
- Both bounds in one pass. Carry two flags,
tight_lowandtight_high, and allow digits in[low[pos] if tight_low else 0, high[pos] if tight_high else 9]. This avoids the subtraction and the decrement (padlowwith leading zeros tohigh's length). - Other bases. Binary digit DP counts integers with no two adjacent 1 bits (LeetCode 600), with exactly set bits, or pairs with a bitwise relation such as , by walking the bits of the bound(s). With two numbers you carry one tight flag per bound.
- Sums instead of counts. Return a pair (count, sum) per state. Appending digit at a position worth to numbers adds to their sum. This gives "sum of all numbers in with property P".
- The -th number with a property (unranking). Compute free counts, then walk from the most significant digit, choosing the smallest digit whose free block still contains the target rank.
- Substring constraints. "Numbers that (do not) contain 13" or "strings between and that avoid an evil word" (LeetCode 1397):
extra= state of a KMP automaton for one pattern, or Aho–Corasick for many. - Divisibility mixes. "Divisible by the sum of its digits" — loop over every possible target sum and run a DP with
extra= (digit sum so far, value mod ). - Digit products and other non-additive summaries. The digit product of a number up to only takes a few thousand distinct values (all of the form ), so a dictionary-keyed memo works where an array would not.
- Counting with very many queries. Precompute the free table indexed by digits remaining once (Rung 4), then answer each query by walking its tight path.
Practice ladder
Easy → hard. Problems are described in our own words; follow the links for the full statements.
1. Count Numbers with Unique Digits (LeetCode 357) — Count with all distinct digits. Teaches the "free block" count without any tight constraint: a pure counting warm-up.
Solution
For each length : 9 choices for the first digit (no leading zero), then 9, 8, 7, … for the rest. Add 10 for the one-digit numbers 0–9.
def count_numbers_with_unique_digits(n: int) -> int:
if n == 0:
return 1
total, ways = 10, 9 # length 1: 0..9
for length in range(2, min(n, 10) + 1):
ways *= 11 - length # 9 * 9 * 8 * 7 * ...
total += ways
return total
assert count_numbers_with_unique_digits(2) == 91 and count_numbers_with_unique_digits(0) == 1
assert count_numbers_with_unique_digits(3) == sum(len(set(str(x))) == len(str(x)) for x in range(1000))
2. Numbers At Most N Given Digit Set (LeetCode 902) — Count positive integers built only from an allowed set of digits. Teaches started and "shorter numbers come free".
Hint
Use the template with a single extra state; a leading zero is allowed even if 0 is not in the set; accept only when started. Closed form: plus a tight walk for length .
3. Number of Digit One (LeetCode 233) — Total count of the digit 1 across . Teaches carrying a counter and returning it at the leaves.
Hint
Either the recursive DP with cnt in the state (full code above) or the per-position formula (Rung 4).
4. Non-negative Integers without Consecutive Ones (LeetCode 600) — Count whose binary form has no two adjacent 1s. Teaches digit DP in base 2.
Solution
extra = previous bit. Leading zeros are harmless here (a 0 bit never creates "11"), so no started flag. Including tight in the lru_cache key is correct — it just also caches the handful of tight states.
from functools import lru_cache
def find_integers(n: int) -> int:
bits = bin(n)[2:]
@lru_cache(maxsize=None)
def go(pos, prev, tight):
if pos == len(bits):
return 1
limit = int(bits[pos]) if tight else 1
total = 0
for b in range(limit + 1):
if b == 1 and prev == 1:
continue
total += go(pos + 1, b, tight and b == limit)
return total
return go(0, 0, True)
assert [find_integers(n) for n in (5, 1, 2)] == [5, 2, 3]
for n in range(0, 3000):
assert find_integers(n) == sum("11" not in bin(x) for x in range(n + 1))
5. Counting Numbers (CSES 2220) — Count integers in with no two adjacent equal digits, . Teaches and started.
Hint
no_equal_adjacent above. Watch : then subtract nothing.
6. Digit Sum (AtCoder DP Contest S) — Count with digit sum divisible by , where has up to 10,000 digits. Teaches string bounds, the modulus, and iterative DP.
Hint
The iterative template in Implementation is a complete solution; subtract 1 for .
7. Count Special Integers (LeetCode 2376) — Count with all distinct digits. Teaches a bitmask extra.
Hint
count_special above: mask of used digits, leading zeros do not set bit 0.
8. Numbers With Repeated Digits (LeetCode 1012) — Count with at least one repeated digit. Teaches counting the complement.
Solution
from functools import lru_cache
def num_dup_digits_at_most_n(n: int) -> int:
s = str(n)
@lru_cache(maxsize=None)
def go(pos, mask, tight, started):
if pos == len(s):
return 1 if started else 0
limit = int(s[pos]) if tight else 9
total = 0
for d in range(limit + 1):
if not started and d == 0:
total += go(pos + 1, mask, tight and d == limit, False)
elif not mask >> d & 1:
total += go(pos + 1, mask | 1 << d, tight and d == limit, True)
return total
return n - go(0, 0, True, False)
assert [num_dup_digits_at_most_n(n) for n in (20, 100, 1000)] == [1, 10, 262]
9. Classy Numbers (Codeforces 1036C) — Many queries: count integers in with at most three nonzero digits. Teaches pruning on a small counter and multi-query use.
Solution
from functools import lru_cache
def classy_up_to(n: int) -> int: # x in [0, n] with at most 3 non-zero digits
s = str(n)
@lru_cache(maxsize=None)
def go(pos, nonzero, tight):
if nonzero > 3:
return 0
if pos == len(s):
return 1
limit = int(s[pos]) if tight else 9
return sum(go(pos + 1, nonzero + (d != 0), tight and d == limit)
for d in range(limit + 1))
return go(0, 0, True)
def classy(lo: int, hi: int) -> int:
return classy_up_to(hi) - classy_up_to(lo - 1)
assert [classy(1, 1000), classy(1024, 1024), classy(65536, 65536), classy(999999, 1000001)] == [1000, 1, 0, 2]
assert all(classy_up_to(n) == sum(sum(c != "0" for c in str(x)) <= 3 for x in range(n + 1))
for n in range(0, 3000, 7))
lru_cache is rebuilt per call here; for queries, hoist a free table indexed by digits remaining (Rung 4).
10. Count of Integers (LeetCode 2719) — Count in (strings up to 22 digits) with digit sum between two limits. Teaches and safe pruning.
Solution
from functools import lru_cache
def count_good(num1: str, num2: str, min_sum: int, max_sum: int) -> int:
MOD = 10**9 + 7
def f(n: str) -> int: # x in [0, n] with min_sum <= digit sum <= max_sum
@lru_cache(maxsize=None)
def go(pos, total, tight):
if total > max_sum:
return 0 # prune: sums only grow
if pos == len(n):
return 1 if total >= min_sum else 0
limit = int(n[pos]) if tight else 9
return sum(go(pos + 1, total + d, tight and d == limit)
for d in range(limit + 1)) % MOD
return go(0, 0, True)
own = 1 if min_sum <= sum(map(int, num1)) <= max_sum else 0
return (f(num2) - f(num1) + own) % MOD
assert count_good("1", "12", 1, 8) == 11
assert count_good("1", "5", 1, 5) == 5
11. Count Stepping Numbers in Range (LeetCode 2801) — Stepping numbers between two 100-digit strings, mod . Teaches previous-digit state with started and string decrement.
Hint
count_stepping_numbers above.
12. Number of Beautiful Integers in the Range (LeetCode 2827) — Count integers in a range that have as many even as odd digits and are divisible by . Teaches a combined state (balance, remainder) and started (leading zeros must not count as even digits).
Hint
extra = (even − odd balance, value mod ). Accept when started, balance 0 and remainder 0.
13. Beautiful numbers (Codeforces 55D) — Count numbers in a range divisible by each of their nonzero digits. Teaches compressing a state with lcm: remember the value mod 2520 and the lcm of digits seen.
Hint
2520 = lcm(1..9) has 48 divisors, so the state is (pos, value mod 2520, index of lcm among 48) ≈ 19 × 2520 × 48. Memoise free states once across all queries (index by digits remaining).
14. Find All Good Strings (LeetCode 1397) — Count strings between two bounds (over lowercase letters) that avoid an "evil" substring. Teaches digit DP over letters with two tight flags and a KMP automaton as extra.
Hint
State (pos, KMP matched length, tight_low, tight_high). Reject when the matched length reaches the evil word's length. See KMP for the failure function.
Common mistakes & interview follow-ups
"Why can you memoise on (pos, rem) without the actual prefix?" Because the future check depends only on the automaton state. Two prefixes with the same remainder and the same freedom have identical sets of good completions (Claim 4).
"Why not memoise tight states?" They lie on a single path and are visited once each; caching them is useless, and caching them under a key without tight is wrong (show the 70 vs 69 example).
"How do you handle when is a 100-digit string?" Either decrement the string or use ; do everything mod and fix negative remainders.
"What if the property is 'the number is divisible by 7'?" Change extra to the value mod 7 with update (r * 10 + d) % 7. Then ask: "and divisible by its digit sum?" — loop over possible digit sums (at most ).
"Can you find the -th such number instead of counting?" Yes: compute free counts, then go digit by digit, skipping whole free blocks while exceeds their size.
"Can you do it without recursion?" Yes: push ways[tight][started][extra] forward digit by digit (the main implementation).
"What is the complexity?" — logarithmic in . Make sure you can say what is for your state.
Mistakes interviewers watch for: leading zeros counted as digits; tight missing from the cache key; forgetting that itself may be good; counting 0 when the problem starts at 1; an off-by-one in ; int overflow in sums; parsing a string bound into a long.
Quick quiz
1. In Trace 1, why does every first digit 0, 1 or 2 contribute exactly 20?
Answer
Once the first digit is below 3 the last two digits are free: all 100 endings 00–99 are allowed. Their digit sums are spread evenly over the five remainders mod 5 (20 each), so exactly 20 endings bring the total to a multiple of 5, whatever the first digit was.
2. How many tight states does a digit DP for visit?
Answer
Ten: one per position 0 through 9. A tight prefix must equal 's prefix, so there is exactly one at each length.
3. Count with no two adjacent equal digits, correctly and with padded strings. Which is which and why do they differ?
Answer
Correct: 273. Padded literally: 263. The padded version reads 1–9 as 001–009 (two equal zeros) and 0 as 000, wrongly rejecting ten numbers. The started flag fixes it.
4. You compute and then with the same pos-indexed memo and get 128 for . Why?
Answer
"Position 1" means two digits remain for 345 but only one for 99. The free counts stored for 345 describe two-digit completions, so reads answers for the wrong length. Reset the memo or index it by digits remaining.
5. For LeetCode 902 with digits {1, 3, 5, 7} and , why is the answer 20 and not 24 or 16?
Answer
4 one-digit numbers and 16 two-digit numbers are all below 100. Three-digit numbers would have to be at most 100, so they must start with 1 and continue with 0 — not allowed. 4 + 16 = 20.
6. What extra would you use to count numbers in that are divisible by 7 and have digit sum divisible by 7?
Answer
The pair (value mod 7, digit sum mod 7): 49 states, updated as ((r * 10 + d) % 7, (s + d) % 7), accepting (0, 0).
Further reading / sources
- AtCoder Educational DP Contest, S — Digit Sum: the standard first digit DP; its samples are used in this lesson's tests.
- LeetCode problems 233, 902, 2376 and 2801: the worked examples (their published examples are asserted in the code).
- Michael Sipser, Introduction to the Theory of Computation, 3rd ed., chapter 1 — finite automata and the product construction that underlies "property automaton × () automaton".
- Robert Sedgewick and Philippe Flajolet, An Introduction to the Analysis of Algorithms, 2nd ed. — counting strings and words with generating functions, the analytic view of the free-block counts.
- cp-algorithms, Introduction to Dynamic Programming — memoization vs tabulation background. (We are not aware of a dedicated cp-algorithms article on digit DP; most write-ups are contest blogs and editorials.)
- Python documentation,
ipaddress.summarize_address_range;to-regex-rangeon GitHub.
Lessons: previous — SOS DP · next — Broken-Profile DP · module — Dynamic Programming · course — DSA: Zero to Mastery.
Related Archon pages: Prefix Sums · Bit Manipulation · Recursion & Induction · KMP · Aho–Corasick · Bitmask DP · Counting & Combinatorial DP · Combinatorics · Modular Arithmetic.