DPAlgorithmaka digit dynamic programming, counting numbers by digits

Digit DP

Count numbers in [0, N] with a digit property by scanning N's digits with a "tight" flag and a small property state.

Pattern: Dynamic ProgrammingPractice (2)
Progress

Overview

Digit DP answers "how many integers in [L, R] satisfy a property of their decimal (or binary) digits?" for R up to 10^18 — far too many to enumerate. The trick is to build numbers digit by digit from the most significant position, tracking (1) pos — how many digits are placed, (2) tight — whether the prefix so far equals N's prefix (so the next digit is capped at N[pos]), (3) started — whether a non-zero digit has appeared (to handle leading zeros), and (4) a small property state such as digit sum mod k, last digit, a mask of used digits, or "contains 13 so far".

Answer [L, R] as count(R) - count(L - 1). States are ≈ 19 × 2 × 2 × |property|; transitions try 10 digits; total work is tiny. The technique is almost always written top-down with Memoization (Top-Down DP) because the tight branch makes bottom-up iteration awkward — and note that memo entries with tight = true are visited at most once per position, so caching only the tight = false states is enough.

Members: count numbers with no repeated digits, numbers whose digit sum is divisible by k, numbers without a given substring (no "13"), numbers with at most k odd digits, sum of digits of all numbers ≤ N, numbers with monotone digits, "count of 1s in all numbers ≤ N".

digitscountingtight flagleading zerosN ≤ 10^18O(digits × states × 10)

Intuition

A mental model before the formal terms.

Imagine typing a number on a keypad while looking at N. As long as every digit you typed matches N so far you are "tight": the next key can be at most N's next digit. The moment you press a smaller key, you are free — anything goes for the rest, and the count of completions depends only on how many positions remain and the property state, not on the exact prefix. That "free" count is what the memo stores and reuses across thousands of prefixes.

Leading zeros are the other subtlety: 007 is the number 7, so the "no repeated digits" property must ignore zeros before the first real digit. The started flag says whether we are still in the leading-zero zone.

How it works

  1. State: f(pos, tight, started, prop) = number of valid completions from position pos given the flags and the property accumulator prop.
  2. Transition: hi = N[pos] if tight else 9; for d in 0..hi: new tight = tight and d == hi; new started = started or d != 0; new prop = update(prop, d) (skipping the update while not started if leading zeros must not count); sum the results, pruning early when prop already violates the property.
  3. Base case: pos == len(N): return 1 if prop satisfies the property (and, if required, started), else 0.
  4. Order: implicit via recursion + memo on (pos, tight, started, prop). Answer: f(0, true, false, initial); for a range subtract count(L-1).
  5. Variants: to compute a sum rather than a count, return a pair (count, sum) and combine as sum += d · 10^(remaining) · count_child + sum_child.

Why it works

Every integer in [0, N] corresponds to exactly one root-to-leaf path in the digit tree that never exceeds N's prefix, so summing over the constrained digit choices counts exactly those integers.

Once tight is false the future is independent of the prefix except through prop, so states with equal (pos, started, prop) have equal counts — the memo is sound.

Recognition

How to tell a problem wants this.

  • Count (or sum over) numbers in a range up to 10^9–10^18 satisfying a condition stated in terms of digits.
  • "How many numbers ≤ N have…", "in the range [L, R], count numbers whose digits…".
  • A property that updates digit by digit with small memory (sum mod k, last digit, set of used digits ≤ 2^10, a small automaton state).
“number of ways” → Dynamic Programming“modulo 10^9 + 7” → Math & Number Theory

Interactive visualization

Play, step, change the input. ← → and space work too.

No interactive visualization for this topic yet

Related visualizations are linked under Related.

Pseudocode

1# count numbers in [0, N] with no two adjacent equal digits
2digits = decimal digits of N
3f(pos, tight, started, last):
4  if pos == len(digits): return 1
5  if not tight and memo has (pos, started, last): return it
6  hi = digits[pos] if tight else 9
7  total = 0
8  for d in 0..hi:
9    if started and d == last: continue
10    nstarted = started or d != 0
11    nlast = d if nstarted else -1
12    total += f(pos+1, tight and d == hi, nstarted, nlast)
13  if not tight: memo[(pos, started, last)] = total
14  return total
15return f(0, true, false, -1)

Implementations

1from functools import lru_cache
2 
3# Digit DP: count numbers in a range satisfying a property, by building them
4# one decimal digit at a time. The state carries "am I still hugging the upper
5# bound" (tight) and "have I placed a non-zero digit yet" (started), plus
6# whatever the property needs. Representative example: count numbers in
7# [0, n] whose digits sum to a given value, and count those with no repeats.
8 
9 
101 · lru_cache does the memoisation; tight is part of the key, which is safe
11def count_digit_sum(n: int, target: int) -> int:
12    digits = str(n)
13 
142 · tight means every digit so far equalled the bound, so the next is capped
15    @lru_cache(maxsize=None)
16    def go(pos: int, total: int, tight: bool, started: bool) -> int:
17        if total > target:
18            return 0
19        if pos == len(digits):
20            return 1 if started and total == target else 0
213 · Including tight in the key is correct but caches fewer states;
22        # only O(len) states are ever tight, so the waste is negligible
23        limit = int(digits[pos]) if tight else 9
24        return sum(
25            go(pos + 1, total + d, tight and d == limit, started or d > 0)
26            for d in range(limit + 1)
27        )
28 
29    result = go(0, 0, True, False)
30    go.cache_clear()  # the cache is per-bound, so do not leak it between calls
31    return result
32 
33 
344 · Range queries are two prefix counts: f(hi) - f(lo - 1)
35def count_in_range(lo: int, hi: int, target: int) -> int:
36    a = count_digit_sum(hi, target)
37    return a if lo == 0 else a - count_digit_sum(lo - 1, target)
38 
39 
405 · A different property, same skeleton: digits must all be distinct
41def count_distinct_digits(n: int) -> int:
42    s = str(n)
43 
44    @lru_cache(maxsize=None)
45    def go(pos: int, mask: int, tight: bool, started: bool) -> int:
46        if pos == len(s):
47            return 1 if started else 0
48        limit = int(s[pos]) if tight else 9
49        total = 0
50        for d in range(limit + 1):
51            if started and mask & (1 << d):
52                continue  # digit already used
53            ns = started or d > 0
54            nmask = (mask | (1 << d)) if ns else 0
55            total += go(pos + 1, nmask, tight and d == limit, ns)
56        return total
57 
58    result = go(0, 0, True, False)
59    go.cache_clear()
60    return result
Walkthrough
  1. @lru_cache removes the manual memo table entirely — the four state components become the cache key automatically.
  2. Including tight in the key is *correct* (unlike hand-rolled memoisation, where mixing tight and non-tight states in one table is the classic bug), because the key distinguishes them. Only O(len(digits)) tight states ever exist, so the extra entries cost nothing.
  3. go.cache_clear() after each call is essential: the closure captures digits, so a cache retained across two different bounds would return answers for the wrong number.
  4. int(digits[pos]) converts the character; Python has no - '0' idiom because characters are strings, not integers.
  5. The digit-sum version uses a generator inside sum(), which reads as the mathematical definition; the mask version needs an explicit loop for the continue.
Complexity (this implementation)
time O(digits * states * 10) · space O(digits * states) in the lru_cache

Python integers are unbounded, so this works for arbitrarily large n — the only language here with no range ceiling.

Language notes
  • functools.lru_cache on a closure is the idiomatic Python memoisation and makes digit DP dramatically shorter than the manual-table versions.
  • cache_clear() is mandatory when the cached function closes over per-call data — forgetting it is a subtle cross-call contamination bug.
  • functools.cache (3.9+) is lru_cache(maxsize=None) with a shorter name.
  • Arbitrary-precision integers mean count_digit_sum(10**100, 5) works, which no other language here can do without a bignum library.
Common mistakes in this language
  • Omitting cache_clear(), so a second call with a different bound reads the first call's cached answers.
  • Decorating a module-level go that takes digits as a parameter — correct, but the string then becomes part of every cache key and the memo hit rate collapses.
  • Forgetting the started flag and mis-counting leading zeros.
Language differences that matter here
  • Memoisation: Python @lru_cache handles the state key automatically (and makes including tight safe), while C++ and JS/TS hand-roll a table and must *exclude* tight states to stay correct — the same algorithm with opposite advice.
  • Range: Python integers are unbounded, C++ handles 10^18 with long long, and JS/TS cap at 2^53 unless converted to BigInt.
  • Character-to-digit conversion: C++ c - '0', JS/TS charCodeAt(pos) - 48, Python int(digits[pos]) — only Python has no code-point arithmetic, because its characters are strings.
  • Cache lifetime is a Python-specific hazard: lru_cache on a closure persists across calls, so cache_clear() is required where the other languages simply allocate a fresh table.

Complexity

Best
—
Average
—
Worst
O(D × S × B) — D digits (≤ 19), S property states, B base (10)
Space
O(D × S)

Effectively constant for a single query; a range query is two calls.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Counting or summing over huge integer ranges by a digit-defined property.
  • The property can be tracked with a small state as digits are appended.
  • Multiple range queries — memo the tight = false states once per N, or precompute free counts by remaining length.
Avoid it when
  • The range is small (≤ 10^7) — brute force is simpler and less error-prone.
  • The property depends on the number's value in a non-digit way (primality, divisibility by a large modulus) — the state explodes; use math instead.
  • A closed-form combinatorial count exists (numbers with digit sum s without an upper bound: stars and bars).

Alternatives

CombinatoricsMemoization (Top-Down DP)Sieve of Eratosthenes

Common mistakes

  • Forgetting started, so leading zeros are treated as real zeros (breaks "no repeated digits", "last digit" properties).
  • Caching states that include tight = true under a key that ignores tight — wrong answers; either include tight in the key or skip caching it.
  • Computing count(L-1) when L = 0 (underflow) — special-case it.
  • Off-by-one on whether 0 itself counts as a valid number for the problem.
  • Overflow in 32-bit languages when counts approach 10^18 — use 64-bit.

Interview patterns

  • Count numbers with unique digits / numbers at most N given a digit set.
  • Number of 1 bits or digit 1 occurrences in all numbers ≤ N.
  • Count numbers whose digit sum is divisible by k; count "stepping numbers" in a range.
  • Numbers with repeated digits (= N − count of unique-digit numbers).
Interview questions on this
Mock interviews

Example problems

Count PrimesmediumCounting Bitseasy