Digit DP
Build the number digit by digit with a 'tight' flag and the needed state.
dp[pos][tight][state] counts completions of the prefix.
01The intuition
Start with what you would do by hand
Using only the digits 1, 3 and 5, how many positive numbers are at most 234? By hand you would start listing: 1, 3, 5, 11, 13, 15, 31, 33, 35, 51, 53, 55, 111, 113, 115, … and check each against 234. That works for 234. For the same question with the limit 2,340,000,000 it does not: there are billions of candidates and you cannot write them down.
Notice what made the small case easy. One-digit and two-digit numbers are automatically below 234, so you only had to count them: 3 one-digit numbers and 3 × 3 = 9 two-digit numbers. The only delicate part is three-digit numbers, where the limit 234 actually bites.
Build the structure, one piece at a time
Build the number one digit at a time from the left, side by side with the limit 2-3-4. At each position you are in one of two situations:
- tight: every digit placed so far equals the limit's digit, so the next digit must not exceed the limit's next digit.
- free: some earlier digit was already smaller than the limit's, so any allowed digit may follow.
Keep a count for each (position, situation): how many ways to finish the number from here. Fill it from the right end, where there is exactly one way to finish: place nothing.
| position | limit digit | free | tight |
|---|---|---|---|
| 3 (end) | 1 | 1 | |
| 2 | 4 | 3 × 1 = 3 | digits below 4: {1, 3} → 2 × free[3] = 2; digit 4 not allowed → +0; total 2 |
| 1 | 3 | 3 × 3 = 9 | digits below 3: {1} → 1 × free[2] = 3; digit 3 allowed → + tight[2] = 2; total 5 |
| 0 | 2 | 3 × 9 = 27 | digits below 2: {1} → 1 × free[1] = 9; digit 2 not allowed → +0; total 9 |
So there are 9 three-digit numbers at most 234 (111, 113, 115, 131, 133, 135, 151, 153, 155). Add the shorter numbers, which are all free: 3 + 9 = 12. Total 21. The structure is just a two-column table, position by position, and it never writes a single candidate number down.
Why it is correct
The invariant: tight[p] counts the ways to fill positions p onward given that the prefix so far equals the limit's prefix, and free[p] counts the ways given the prefix is already smaller. From a tight position, choosing a digit below the limit's digit makes the rest free, choosing exactly the limit's digit (if allowed) keeps it tight, and choosing a bigger digit is impossible. From a free position any allowed digit keeps it free. Those are all the cases, and they do not overlap, so adding them counts every valid completion exactly once.
tight[p] = (number of allowed digits < Lp) · free[p+1] + [Lp allowed] · tight[p+1]
Why it is fast
The limit has d digits. For each position there are two situations and at most 10 digits to try, so the work is about 20d steps. A limit of 2,340,000,000 has 10 digits: about 200 steps, instead of billions of candidates. Problems add more state, such as "which digits have been used" (a mask of 10 bits) or "the count of ones so far", and the cost becomes d × (states) × 10, still tiny.
How to recognise it in an interview
Cues: "how many numbers up to N" with a condition on the digits, and N far too large to loop over. Say: I will build the number digit by digit against N, tracking whether I am still tied with N. Numbers At Most N Given Digit Set is exactly the example above. Count Numbers with Unique Digits adds a mask of used digits to the state. Number of Digit One adds a running count of ones.
02The idea in one line
Build the number digit by digit with a 'tight' flag and the needed state.
Reach for it when: Count numbers with unique digits, numbers at most N given digit set, count good numbers.
Cost: O(digits · states · 10) time.
03The walk-through, step by step
The video works one example: Count numbers ≤ 234 using digit set {1,3,5}. These are its captions in order, so you can follow without the video or check a step you missed.
- tight = prefix equals N so far; free = already smaller, anything goes
- At the end there is exactly 1 way to finish (the empty suffix)
- free[2] = 3 choices × free[3] = 3
- free[1] = 3 choices × free[2] = 9
- free[0] = 3 choices × free[1] = 27
- tight[2]: 2 digit(s) below 4 × free[3] + 0 since 4 is not allowed = 2
- tight[1]: 1 digit(s) below 3 × free[2] + tight[2] since 3 is allowed = 5
- tight[0]: 1 digit(s) below 2 × free[1] + 0 since 2 is not allowed = 9
- 3-digit numbers ≤ 234: tight[0] = 9; shorter numbers are free: 3 + 9 = 12
- Total = 9 + 12 = 21
- digits × (tight, free) × choices: O(len · 10), never enumerate 234 numbers
04Asked at Google
5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.
| Problem | Difficulty | Frequency | Reported |
|---|---|---|---|
| Count Numbers with Unique Digits | Medium | 28 | |
| Number of Digit One | Hard | 28 | last 6 months |
| Numbers With Repeated Digits | Hard | 20 | |
| Numbers At Most N Given Digit Set | Hard | 6 | |
| Count Special Integers | Hard | 6 | last 6 months |
05Related patterns
Other patterns in Dynamic Programming: 1-D linear DP, Kadane (best ending here), Longest increasing subsequence, Grid path DP, 0/1 knapsack (subset sum), Unbounded knapsack (coin change), Two-sequence DP (LCS / edit distance), Wildcard / regex matching DP, Palindromes: expand or table, Prefix segmentation DP, Interval DP (last operation), State-machine DP (stocks), Bitmask DP over subsets, Memoised DFS (top-down), Game DP (minimax on a range), Counting ways with modulo, DP over sorted keys (chains).