The site's eleventh dynamic programming entry, and the
first whose table isn't indexed by a position in an array, a range, a bitmask, or a tree node — it's
indexed by a position in the decimal digits of a single number N, carrying one extra bit
of state no other entry on this page's own guide needs: whether the digits
chosen so far still equal N's own digits exactly, or have already fallen strictly below
them. Call the first case tight, the second free. The question:
count how many integers between 0 and N share some digit-level property —
here, digits summing to exactly a target S — without ever listing them one at a time.
Checking every integer directly is O(N); digit DP answers it by walking N's
own digits once.
A ranger station issues trail permits with sequential numbers starting at 0. For an
upcoming raffle, any permit whose digits sum to a chosen lucky number wins. Given the highest permit
issued so far and the lucky sum, count the winners without listing every permit:
highest permit N = 212 — lucky sum S = 6 — digits of N, most significant first:
free[pos][r] — ways to fill positions pos..end freely, digits sum to r
tight[pos][r] — same, but bounded by N's own digit at pos and beyond
Write N's digits as D[0..L-1], most significant first. For every
position pos (0..L, where L means "no digits left") and every remaining
target r (0..S), define two counts:
free[pos][r] = ways to fill positions pos..L-1, each digit freely 0-9, summing to exactly r
tight[pos][r] = same, but the digit at pos can be at most D[pos] — because everything chosen
before pos has matched N exactly, and going over D[pos] here would exceed Nfree[pos][r] = Σ (d = 0..9) free[pos+1][r-d]
tight[pos][r] = Σ (d = 0..D[pos]-1) free[pos+1][r-d] + tight[pos+1][r-D[pos]]Base case: with no digits left (pos = L), the only way to reach a
remaining target of 0 is to add nothing — free[L][0] = tight[L][0] = 1,
every other value at pos = L is 0. The tight formula's split is
the whole trick. Any digit strictly less than D[pos] already puts this number
below N at this position, so everything after it is unconstrained — that term reads from
the free table. Only the single digit exactly equal to D[pos] keeps the bound
alive one more position, so it's the only term that reads tight again, at
pos + 1. That's also why the extra state is nearly free: being tight at
pos requires every earlier digit to already equal D[0..pos-1] exactly, so
there is only ever one tight path through the whole computation, never a whole
table's worth of live tight states the way free needs one. The final answer is
tight[0][S] — bounded by N from the very first digit.
function countDigitSum(N, S) {
const D = String(N).split('').map(Number);
const L = D.length;
const free = Array.from({ length: L + 1 }, () => new Array(S + 1).fill(0));
const tight = Array.from({ length: L + 1 }, () => new Array(S + 1).fill(0));
free[L][0] = 1;
tight[L][0] = 1;
for (let pos = L - 1; pos >= 0; pos--) {
for (let r = 0; r <= S; r++) {
let f = 0;
for (let d = 0; d <= 9; d++) if (r - d >= 0) f += free[pos + 1][r - d];
free[pos][r] = f;
let t = 0;
for (let d = 0; d <= D[pos] - 1; d++) if (r - d >= 0) t += free[pos + 1][r - d];
if (r - D[pos] >= 0) t += tight[pos + 1][r - D[pos]];
tight[pos][r] = t;
}
}
return tight[0][S]; // count of integers in [0, N] whose digits sum to S
}Computing tight the same way as free — letting the digit at a
bound position run 0-9 instead of stopping at D[pos] — silently counts numbers larger
than N. It's tempting to think the two tables should agree once you're "close enough" to the
end, but collapsing tight[pos][r] into free[pos][r] at even one position
throws away the one thing that made it tight in the first place. Take N = 27
(D = [2, 7]), lucky sum S = 3. The true winners in [0, 27] are
3, 12, and 21 — three permits. Collapse tight into
free at the leading digit, and the second digit is treated as free to run 0-9 regardless
of what the first digit was, which also legalizes 30 (digits sum to 3, but
30 > 27) — reporting 4 winners instead of 3. A 3,000-trial
sweep against a brute-force digit-sum scan found this exact bug wrong on 2,387 of
3,000 random (N, S) pairs (79.6%) — the more digits below the corrupted
position, the more out-of-range numbers slip in.
Dropping the + tight[pos+1][r-D[pos]] continuation term loses every number
that has to follow N's own digits all the way to the end — including N itself. The first
sum in the tight formula (digits strictly below D[pos]) is the one that looks like it
"does the real work," and it's easy to write the recurrence with only that sum, treating the exact-
match digit as just another case already covered. It isn't: without the continuation term, nothing
ever counts the single path that matches N at every remaining position. Take
N = 19, lucky sum S = 10. The only permit in [0, 19] whose
digits sum to 10 is 19 itself (1 + 9 = 10) — the true answer is
1. Drop the continuation term, and the recurrence never finds a way to keep matching
N's own digits past the first position, reporting 0 winners — missing the
one and only correct answer entirely. A 3,000-trial sweep found this version wrong on
2,440 of 3,000 random (N, S) pairs (81.3%), including every case where
N itself, or a number sharing a long digit-prefix with it, is the only qualifying
number.
Time: O(D · S) table cells, where D is the number of
digits in N (⌊log₁₀N⌋ + 1) and S is the target sum, each
filled in O(10) work — so O(D · S) overall, ignoring the constant. Unlike
0/1 Knapsack's O(n · W), where W can
be arbitrarily large relative to the input, digit DP's own "capacity" axis is self-bounding: a digit
sum can never exceed 9 · D, so S is always polynomial in the size of
N's own representation — genuinely polynomial, not pseudo-polynomial, the same
distinction this page's own
guide draws between Knapsack and Weighted Interval Scheduling. Space:
O(D · S) for both tables as written, though computing row pos only ever
reads row pos + 1, so — like Unbounded Knapsack's single compressed row — this
compresses to two rolling rows of O(S) each with no loss, since the answer is a count,
not a reconstructed path. For an N in the billions (D ≈ 10) and a target
sum bounded by 9 · D ≈ 90, that's on the order of a few thousand operations, replacing a
brute-force scan of billions of integers.
This site's guide, Choosing a Dynamic Programming Approach, compares this entry against the other ten Dynamic Programming entries side by side.