Advanced Conceptsdigitcounting

Digit DP

Given a range of numbers and a property defined on a number's digits, such as how many times a particular digit appears, count how many numbers within that range satisfy the property.

Do this lesson first: climbing stairs

Example input

range 0 to N with N = 370; property: the digit 7 appears exactly once

Expected output

Break it down

Answer each question out loud before you open it. Getting it wrong here is the useful part. A revealed answer you never guessed at teaches you nothing.

Build the number one digit at a time from the left, and after p digits ask two things: has it already dropped BELOW N, and how many 7s has it used. dp[s][p] is the number of ways to choose the remaining digits p to L - 1 so the finished number has exactly one 7, starting from state s. There are three states. TIGHT means every digit so far copied N's, so the next digit may not exceed N's next digit. FREE0 and FREE1 mean some earlier digit was smaller than N's, so every later digit is free, with no 7 or one 7 used so far. TIGHT needs no 7-count of its own, because its digits are N's digits and N's count is known.

dp[FREE0][p] = 9 × dp[FREE0][p + 1] + dp[FREE1][p + 1]; dp[FREE1][p] = 9 × dp[FREE1][p + 1]; dp[TIGHT][p] = d × dp[FREE_c][p + 1] + dp[TIGHT][p + 1], where d is N's digit at p and c is how many 7s N's first p digits hold

Ask what digit goes at position p, and follow it to the state it leads to. From a free state any of the ten digits is allowed: the nine that are not 7 keep the count where it is, and the 7 raises it by one, so FREE0 gets 9 ways to stay FREE0 plus one way to become FREE1, while FREE1 gets 9 ways to stay FREE1 and a 7 would make two, which can never be undone, so that branch adds nothing. From TIGHT the digit cannot exceed N's digit d. Each of the d smaller digits drops the number below N for good, into the free state with N's count so far (on this page none of them is a 7, since N has no 8 or 9), and copying d itself keeps it TIGHT. Different digits give different numbers, so the branches add.

The END column, past the last digit, is given. A free number that finished with exactly one 7 counts once: dp[FREE1][END] = 1 and dp[FREE0][END] = 0. A TIGHT number that reaches END is N itself, so dp[TIGHT][END] is 1 if N has exactly one 7 and 0 if not. Every other cell reads only the column to its right, so the table fills right to left, the reverse of the order the digits are chosen in. That is the memoized recursion count(position, state) turned into a table: the recursion starts at position 0, but it cannot answer until the calls for the later positions have returned.

Tabulation, and tiny: 3 states times L + 1 positions, each cell a handful of additions, so the work grows with the NUMBER OF DIGITS of N rather than with N. Counting from 0 to 3705 one number at a time means 3706 checks; the table for 3705 has 15 cells. Two things are worth noticing in the filled table. The free rows never look at N at all, so they are the same for every N with the same number of digits and could be reused across many queries. And the TIGHT row is a single path: there is exactly one prefix that copies N's first p digits, so that row only ever holds what is still possible along N itself.

Time O(L × S × 10) for L digits and S states, here O(L)Space O(L × S), reducible to O(S) with two columns

Fill the table

The table pauses before each cell you have to supply. Type the value the recurrence gives, and the write animation confirms it.

Step not started

Press start. The animation stops at every cell YOUR recurrence must fill.

Rows ↓
Cols →

END

FREE0

243

FREE1

729

TIGHT

Rows ↓state: FREE0 and FREE1 are already below N with no 7 or one 7 so far; TIGHT still equals N digit for digit

Cols →position p, headed by N's digit there; END is past the last digit

digit-dp.ts

1function countOneSeven(N) {
2 const d = [...String(N)].map(Number), L = d.length;
3 const FREE0 = 0, FREE1 = 1, TIGHT = 2; // below N with no 7 / one 7, or still equal to N
4 const dp = [[], [], []];
5 dp[FREE0][L] = 0; dp[FREE1][L] = 1; dp[TIGHT][L] = d.filter((x) => x === 7).length === 1 ? 1 : 0;
6 for (let p = L - 1; p >= 0; p--) {
7 const seen = d.slice(0, p).filter((x) => x === 7).length; // 7s in N's first p digits
8 for (const s of [FREE0, FREE1, TIGHT]) {
9 const top = s === TIGHT ? d[p] : 9; // a tight number cannot go above N's digit
10 let total = 0;
11 for (let x = 0; x <= top; x++) {
12 const sevens = (s === TIGHT ? seen : s) + (x === 7 ? 1 : 0);
13 if (sevens > 1) continue; // a second 7 can never be undone
14 const next = s === TIGHT && x === top ? TIGHT : sevens; // copying N's digit stays tight
15 total += dp[next][p + 1];
16 }
17 dp[s][p] = total;
18 }
19 }
20 return dp[TIGHT][0];
21}

Base caseComputedBeing readAnswer

The code, the trap, the variations

digit-dp.ts

1function countOneSeven(N) {
2 const d = [...String(N)].map(Number), L = d.length;
3 const FREE0 = 0, FREE1 = 1, TIGHT = 2; // below N with no 7 / one 7, or still equal to N
4 const dp = [[], [], []];
5 dp[FREE0][L] = 0; dp[FREE1][L] = 1; dp[TIGHT][L] = d.filter((x) => x === 7).length === 1 ? 1 : 0;
6 for (let p = L - 1; p >= 0; p--) {
7 const seen = d.slice(0, p).filter((x) => x === 7).length; // 7s in N's first p digits
8 for (const s of [FREE0, FREE1, TIGHT]) {
9 const top = s === TIGHT ? d[p] : 9; // a tight number cannot go above N's digit
10 let total = 0;
11 for (let x = 0; x <= top; x++) {
12 const sevens = (s === TIGHT ? seen : s) + (x === 7 ? 1 : 0);
13 if (sevens > 1) continue; // a second 7 can never be undone
14 const next = s === TIGHT && x === top ? TIGHT : sevens; // copying N's digit stays tight
15 total += dp[next][p + 1];
16 }
17 dp[s][p] = total;
18 }
19 }
20 return dp[TIGHT][0];
21}

Where people go wrong

Forgetting the tight flag, and counting every string of L digits with exactly one 7. For N = 370 that is 3 × 81 = 243, every number from 000 to 999 with one 7, against the true 62; the 243 is sitting in the table as dp[FREE0][0], the count for a number that is already free before its first digit. That state, like dp[FREE1][0] beside it, is one no real number is ever in at position 0; the table fills it anyway, because a free row is computed for every position without asking whether anything can arrive there. The cap only binds while the prefix still equals N, which is exactly what TIGHT tracks. The opposite slip is to keep the cap after the number has dropped below N, so that after a first digit of 2 the next two digits are still held to at most 7 and at most 0. That finds only 4 of the 62, because 2 is already below 3 and everything after it should be free.

Count over a range from A to B instead of from 0.
Run the same table twice and subtract: the count up to B minus the count up to A - 1, taking that second count as 0 when A is 0. Nothing inside the table changes; the range is handled outside it, which is also why the answer is not any single cell of either table.
Let N contain an 8 or a 9.
The states and the order are unchanged, but a TIGHT cell gains a third term. With N's digit at 8 or 9, the 7 is now one of the smaller digits, so it goes to the free state with one more 7 (or nowhere, if N's prefix already holds a 7) while the other d - 1 smaller digits go to the free state with the same count. This page keeps N's digits at 7 or below so every TIGHT cell has exactly two terms.
Count the digit 0 instead of the digit 7.
Leading zeros stop being harmless: 037 would look like it holds a 0. The state needs one more flag, whether a non-zero digit has been placed yet, and zeros before it are not counted. The TIGHT cell also loses its two-term shape, since 0 is among the smaller digits whenever N's digit is at least 1, and the number 0 itself needs a special case. The right-to-left order and the END column are unchanged.
Ask for numbers whose digit sum is divisible by k.
Replace the 7-count with the digit sum modulo k, so the free part has k rows instead of two. The right-to-left order and the END column work as here, but a TIGHT cell now spreads its smaller digits over several residue rows instead of sending them all to one.

Traveling Salesman Problem Sum over Subsets