“How many numbers from 0 to a billion have digits summing to 20?” Looping to a billion is hopeless. Digit DP counts them by building numbers one digit at a time, left to right, and dynamic-programming over the choices. The crucial piece of state is a tight flag: is the prefix we’ve placed so far still exactly equal to N’s prefix? If it is, the next digit is capped at N’s digit; the moment we place something smaller, the rest of the positions are free to be anything, and their count follows from a small precomputed table. Watch the total assemble position by position.
O(digits × states) not O(N) · the “tight” flag caps digits to N · count, don’t enumerate
tight
True while the prefix equals N’s prefix — then the next digit is capped at N’s digit.
free
Once a smaller digit is placed, remaining positions can be anything (0–9).
property state
What you track to test the property — here the digit sum so far.
the count
Sum over positions of the free completions, plus N itself if it qualifies.
digit-dp.js — build a number, digit by digit
Ready
Counting numbers in [0, N] whose digits sum to S. We walk N’s digits left to right. At each position, placing a digit below N’s digit frees the rest — we add all free completions. Step through the positions.
–
position
–
added here
0
count so far
How it works
The insight is that once you deviate below N at some position, everything after is unconstrained — so you can count those completions in bulk instead of one by one. Precompute F[p][s] = how many p-digit strings have digit sum exactly s. Now walk N’s digits with a running sum. At position i, for each digit d strictly less than N’s digit there, the remaining positions are free, so add F[remaining][S − sumSoFar − d]. Then commit to N’s actual digit (staying tight) and move on. After the last position, if the accumulated sum equals S, add one for N itself. The total number of states is roughly digits × sum × 2, so this runs in the number of digits, not in N.
1
Precompute free completions
Build F[p][s] = the number of p-digit strings (each digit 0–9) whose digits sum to s. This lets you count unconstrained tails in one lookup.
2
Walk N’s digits, tracking the sum
Go left to right keeping the sum of digits placed so far, staying “tight” — equal to N’s prefix.
3
Below N’s digit → free the tail
At each position, for every digit smaller than N’s digit there, the remaining positions are free: add F[remaining][S − sumSoFar − digit]. Then set the digit to N’s and continue tight.
✓
Add N itself if it qualifies
After the last digit, if the tight number (N itself) has digit sum S, add one. The total is the count in [0, N] — computed in O(digits × states), never looping to N.
Time
O(digits × states)
vs brute
O(N)
Key state
“tight” flag
Counts
not enumerates
The code
# count numbers in [0, N] with digit sum == Sfrom functools import lru_cache
digits = list(map(int, str(N)))
@lru_cache(None)
def go(pos, cur_sum, tight):
if pos == len(digits):
return 1 if cur_sum == S else 0
hi = digits[pos] if tight else 9 # cap when tight
total = 0
for d in range(hi + 1):
total += go(pos + 1, cur_sum + d, tight and d == hi)
return total
answer = go(0, 0, True)
Quick check
1. What does the “tight” flag track in digit DP?
Tight means the prefix still equals N’s prefix. While tight, the next digit can’t exceed N’s digit at that position. The moment you place a smaller digit, you become “free” and the rest can be anything.
2. Why is digit DP faster than checking every number up to N?
Once a position goes below N’s digit, the remaining positions are unconstrained and their qualifying completions are counted in bulk from a table. So the work is proportional to digits × states — logarithmic in N, not linear.
3. After walking all of N’s digits while staying tight, what remains to check?
The tight path that never deviates spells out N exactly. It was never counted by the “place a smaller digit” branches, so at the end you add one if N itself satisfies the property.
FAQ
What is digit DP?
A DP technique for counting how many numbers in a range satisfy a digit-based property (target digit sum, no equal adjacent digits, divisibility…). It builds numbers digit by digit and memoizes over (position, a "tight" flag, property state), running in time proportional to the number of digits, not the range size.
What is the “tight” flag for?
It records whether the chosen prefix exactly matches N’s prefix. While tight, the next digit is capped at N’s digit (else you overshoot N). Placing a smaller digit makes you "free" — later positions can be 0–9. The flag is what keeps the count within [0, N].
What kinds of problems does digit DP solve?
Counting numbers in [L, R] by digit sum, adjacency constraints, divisibility (tracking remainder), containing/avoiding digits, palindromes, or bounded digit counts — with ranges via count(R) − count(L−1). A competitive-programming staple for counting by digit properties over huge ranges.
How do you handle a range [L, R] instead of [0, N]?
With the prefix trick: answer for [L, R] = count(R) − count(L−1), where count(x) is the digit-DP count in [0, x]. Any range reduces to two calls of the single-bound version, which is why digit DP is written to count up to one bound.