Digit DP
Counting the numbers up to N with some property of their digits sounds like a loop over N numbers, but the digits can be placed one at a time from the left, and the only thing the count depends on is whether the digits placed so far still match N exactly. That is the tight flag: while tight, the next digit may not exceed N's digit; once a smaller digit has been chosen, the rest is free and every allowed digit goes. Two states per position, filled from the last position backwards, and the answer is the tight state at the first position. Adding state, a digit sum, a remainder, a last digit, is what turns the same table into an answer for harder properties.
How many numbers from 0 to 275 never contain the digit 7? Checking each number is O(n). Instead, place digits from the left. Each column holds, for each state, the number of ways to fill that position and everything after it: "tight" means the digits so far match 275 exactly, so the next digit may not go above the digit 275 has there; "free" means a smaller digit was already chosen and anything allowed goes. Fill from the right, where an empty suffix counts as one number.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.
Position 2 is tight and 275's digit here is 5. How many ways complete the number?
Answer: 6. Digits below 5 go free: 5 x 1. The digit 5 itself stays tight, adding 1.
Position 1 is tight and 275's digit here is 7. How many ways complete the number?
Answer: 63. Digits below 7 go free: 7 x 9. The digit 7 itself stays tight, but it is forbidden, so it adds 0.
Position 0 is tight and 275's digit here is 2. How many ways complete the number?
Answer: 225. Digits below 2 go free: 2 x 81. The digit 2 itself stays tight, adding 63.
How it runs, step by step
How many numbers from 0 to 275 never contain the digit 7? Checking each number is O(n). Instead, place digits from the left. Each column holds, for each state, the number of ways to fill that position and everything after it: "tight" means the digits so far match 275 exactly, so the next digit may not go above the digit 275 has there; "free" means a smaller digit was already chosen and anything allowed goes. Fill from the right, where an empty suffix counts as one number.
Digit DP counting numbers up to 275 without the digit 7.
Position 2, free: any of the 9 allowed digits can go here, and the rest is still free, so 9 x 1 = 9.
Free at position 2: 9.
Position 2, tight: 275 has the digit 5 here. A digit below 5 frees the rest: 5 allowed choices x 1 = 5. Choosing 5 itself keeps the number tight, adding the tight count of the next position, 1. Total 6.
Tight at position 2: 6.
Position 1, free: any of the 9 allowed digits can go here, and the rest is still free, so 9 x 9 = 81.
Free at position 1: 81.
Position 1, tight: 275 has the digit 7 here. A digit below 7 frees the rest: 7 allowed choices x 9 = 63. Choosing 7 itself keeps the number tight, but 7 is the forbidden digit, so that branch adds nothing. Total 63.
Tight at position 1: 63.
Position 0, free: any of the 9 allowed digits can go here, and the rest is still free, so 9 x 81 = 729.
Free at position 0: 729.
Position 0, tight: 275 has the digit 2 here. A digit below 2 frees the rest: 2 allowed choices x 81 = 162. Choosing 2 itself keeps the number tight, adding the tight count of the next position, 63. Total 225.
Tight at position 0: 225.
225 numbers from 0 to 275 never use the digit 7, read from the tight cell at position 0. The table has 2 x 3 cells for a 3-digit limit, so the count is O(digits) however large 275 is; a limit with twenty digits costs forty cells, not a scan of a twenty-digit number. Shorter numbers ride along as leading zeros, which is why forbidding 0 itself would need a third flag for "has the number started". The pattern generalises by adding state: a running digit sum, a remainder, or whether a digit has repeated, each multiplying the rows.
225 numbers without the digit 7.
Write it yourself
Define countWithoutDigit(n, digit) and return how many numbers from 0 to n do not contain the digit; 0 counts. It runs in your browser against this lesson's own 3 examples.
// Walk the digits of n from the left, counting what is free below each prefix rather than testing every number. The count starts at 0, which contains no digit at all.function countWithoutDigit(n, digit) { return 0;}
Remember
- Place digits from the left; the tight flag says whether the prefix still equals N's prefix.
- Tight: digits below N's digit go free, N's digit itself stays tight; free: every allowed digit goes.
- Fill from the right, one column per position; harder properties add rows of state, never more columns.
Topics covered
Where this is used
NetworkingSplitting an address range into CIDR blocks
Security groups and route tables take prefixes like 10.0.0.0/22, not arbitrary endpoints, so covering 10.0.0.5 through 10.0.3.200 means splitting it into whole blocks first, which is what Python's ipaddress.summarize_address_range does. It walks the bits of each bound from the left the way this walks digits: while the prefix still equals the bound nothing can be emitted, and the first bit where it drops below leaves every later bit free, which is exactly one prefix. That is why a range over W-bit addresses never needs more than 2W - 2 prefixes, one per bit position along each of the two boundary paths.
Text indexingRank queries in a wavelet tree
Libraries that build an FM-index on a wavelet tree, such as sdsl-lite's csa_wt or NVBIO's protein search, have to answer how many values in a block are smaller than x while the data stays compressed. The tree answers it one bit of x per level: where x has a 1, everything holding a 0 at that position is already smaller whatever its lower bits are, so the whole side is added in a single step, while the walk carries on down x's own bit path. That bit path is the tight state and the side added wholesale is the free one, so the count falls out of a single root-to-leaf walk instead of a scan.
GeospatialCovering a map region with index cells
A 2dsphere index in MongoDB, like Google Maps and Foursquare before it, sits on the S2 library, which answers a region query by covering the region with cells off a quadtree over the sphere. The coverer starts at the six cube faces and keeps splitting: a cell the region fully contains is terminal and goes in whole, and only a cell straddling the edge is subdivided again. Contained is the free state and straddling is the tight one, so the work is bounded by the boundary path rather than by the area, and a cell budget caps how far that path is followed.
DatabasesRank and count in Redis sorted sets
ZRANK and ZCOUNT report how many members sit below a score without touching them, because every forward pointer in the skiplist carries a span, the number of members it skips over. The walk starts at the top level and adds the span of each jump that stays below the target, dropping a level only when the next jump would overshoot, so whole runs are counted in one step and only the boundary path is descended. Those stored spans play the part the memo table plays here: the free side is a number you already have rather than a subtree you still have to visit.
Why it works this way
Why place digits from the left and not the right?
Whether a number is at most N is decided at the first position where the two differ, and nothing after that position can change the verdict. Working left to right is what lets that comparison collapse into a single bit of state, still equal or already below, and once it is already below the bound is finished with. From the right you would have to carry every digit placed so far to know what is still allowed, which is the same as not summarising at all.
Once free, never tight again
The recursive call passes tight && d == limit, and dropping the tight && is the bug that catches nearly everyone the first time. In the free state limit is 9, so without that guard a prefix that had already gone below N snaps back to tight the moment a 9 is chosen, clamping the rest of the number to N's digits and losing a large part of the count. The flag is deliberately one-way: dropping below the bound at any position frees every position after it for good.
Leading zeros are not the same as the digit zero
Every number is placed as a fixed-width string, so 7 under a bound of 275 is built as 007 and those padding zeros look like real digits to the recursion. For never uses a 7 that does no harm, but for anything that reads the digits themselves, no zero anywhere, strictly increasing digits, how many distinct digits, the invented zeros give a wrong answer. The fix is a second flag, usually called started, false while only zeros have been placed and true from the first nonzero digit, so the positions before it are skipped rather than counted as zeros.
Every piece of state has to be in the memo key
There is only one tight prefix at each position, N's own, so (pos, true) is computed once and never read back again; all of the reuse lives in (pos, false), where every prefix that has already dropped below N arrives. That is also where the quiet wrong answer comes from once you add state: put a running digit sum or a remainder mod m into the recursion and leave it out of the key, and two prefixes with different sums share one cached number. The key has to hold exactly what the rest of the count depends on, no less, and no more or it stops hitting.
Read more
- Digit DPUSACO Guide
- S - Digit SumAtCoder Educational DP Contest · atcoder.jp
- Counting NumbersCSES 2220 · cses.fi
- Wavelet TreeWikipedia
- Classless Inter-Domain RoutingWikipedia
- S2 Cell HierarchyS2 Geometry