Digit DP

“How many integers between 1 and $10^{18}$ have no two adjacent equal digits?” There are $10^{18}$ candidates and one second of budget, so iteration is dead on arrival. But the answer does not depend on the numbers — it depends on their digits, and there are only 18 of those. Digit DP is the technique that turns a range of size $10^{18}$ into a walk over 18 positions with a handful of states at each one.

The whole pattern rests on a single observation, and everything else is bookkeeping: as you build a number digit by digit from the most significant end, there is only ever one prefix still equal to the bound’s prefix. Every other prefix has already dropped below the bound and is therefore free to use any digit at all. One tight branch, one free bucket. That is the state.

What you’ll learn

• The tight/free split and why it collapses an exponential search into $O(n)$ columns.
• The memoized-recursion template you can write from memory in an interview, and where each problem’s own logic plugs into it.
• Why started (the leading-zero flag) is a separate piece of state from tight, and which problems need it.
• How to answer a range query $[L, R]$ when the technique only counts $[0, N]$.
• The two bugs that produce almost-right answers: memoizing across tight, and dropping the final + tight.

The cue

You are looking at digit DP when…

• The question is “how many numbers in a range”, not “which number” — a count, or occasionally a sum.
• The range bound is enormous: $10^9$, $10^{18}$, or given as a string because it does not fit in a machine int.
• The property being counted is a property of the decimal (or binary) digits — digit sum, forbidden digits, repeated digits, adjacent digits, digits drawn from a set, divisibility by a small modulus.

The reframe: stop thinking of the interval as a set of numbers. Think of it as the set of digit strings of length len(N) that are lexicographically ≤ N. Then walk left to right and ask, at each position, “am I still pinned to the bound, or am I already below it?”

Reach for something else when the range is small enough to iterate (up to a few million, just loop — it is shorter and unarguably correct), when you need the $k$-th such number rather than the count (that is a binary search on top of a digit DP counter), or when the property is arithmetic rather than digital — “how many multiples of 7 in $[L, R]$” is one division, not a DP.

Visual intuition

Two rows: the single tight prefix on top, the accumulated free prefixes below. Watch how nothing ever flows back up — once free, always free.

stateCounting numbers in [0, 325] with no digit 4tight/free · O(len N) columns

order325

1def count(N: str, bad: str) -> int:2    tight, free = 1, 0        # one tight prefix: the empty one3    for ch in N:4        d = int(ch)5        below = sum(1 for x in range(d) if str(x) != bad)6        free = free * 9 + tight * below   # free stays free; tight breaks free7        tight = tight if ch != bad else 08    return tight + free       # + tight counts N itself

tight1free0forbidden4

startCounting how many integers in [0, 325] contain no digit 4, by scanning the bound **left to right** and tracking only two things: how many prefixes so far are still equal to 325's prefix (**tight**, row 0) and how many have already dropped below it (**free**, row 1). Before any digit is placed there is exactly one tight prefix — the empty one — and no free prefix.

Play‹›1/5⟲

The tight row never holds more than 1, because exactly one prefix can equal the bound's prefix. That single fact is why an interval of size 10^18 costs 18 columns. The number under each node is how many prefixes of that length are in that state.

And here is the case that makes the tight branch’s fragility visible — a bound whose own digit is the forbidden one:

stateWhen the bound itself is illegal: N = 440, digit 4 forbiddenthe tight branch dies

order440

1def count(N: str, bad: str) -> int:2    tight, free = 1, 0        # one tight prefix: the empty one3    for ch in N:4        d = int(ch)5        below = sum(1 for x in range(d) if str(x) != bad)6        free = free * 9 + tight * below   # free stays free; tight breaks free7        tight = tight if ch != bad else 08    return tight + free       # + tight counts N itself

tight1free0forbidden4

startCounting how many integers in [0, 440] contain no digit 4, by scanning the bound **left to right** and tracking only two things: how many prefixes so far are still equal to 440's prefix (**tight**, row 0) and how many have already dropped below it (**free**, row 1). Before any digit is placed there is exactly one tight prefix — the empty one — and no free prefix.

Play‹›1/5⟲

At position 0 matching the bound digit would place a forbidden 4, so tight drops to 0 and stays there. From that column on, every count comes from the free row -- and the final '+ tight' correctly adds nothing, because 440 is not one of the numbers being counted.

The template

Two forms. The iterative one matches the pictures above and is the one to reason with; the memoized recursive one is what you actually write in an interview, because extra state is a parameter rather than another array.

digit_dp.py

from functools import lru_cache
 
 
def count_no_digit_iterative(bound: str, bad: str) -> int:
    """Numbers in [0, bound] that never use the digit `bad`. Leading zeros allowed."""
    tight, free = 1, 0                       # one tight prefix: the empty one
    for ch in bound:
        d = int(ch)
        below = sum(1 for x in range(d) if str(x) != bad)
        free = free * 9 + tight * below      # free stays free; tight can break free
        tight = tight if ch != bad else 0    # matching the bound may be illegal
    return tight + free                      # the surviving tight prefix IS `bound`
 
 
def count_no_digit(bound: str, bad: str) -> int:
    """The same thing as memoized recursion -- the shape that generalises."""
    n = len(bound)
 
    @lru_cache(maxsize=None)
    def go(pos: int, tight: bool) -> int:
        if pos == n:
            return 1                          # a complete, legal digit string
        total = 0
        hi = int(bound[pos]) if tight else 9  # `tight` caps this position
        for d in range(hi + 1):
            if str(d) == bad:                 # <-- the ONLY problem-specific line
                continue
            total += go(pos + 1, tight and d == hi)
        return total
 
    result = go(0, True)
    go.cache_clear()                          # LeetCode reuses the instance
    return result
 
 
print(count_no_digit_iterative("325", "4"), count_no_digit("325", "4"))  # 266 266
print(count_no_digit_iterative("440", "4"), count_no_digit("440", "4"))  # 324 324
print(count_no_digit_iterative("1000", "4"))                             # 730

The recursive form is the template worth memorising, because every problem in the family is this skeleton with one or two extra parameters:

skeleton.py

@lru_cache(maxsize=None)
def go(pos, tight, started, extra):
    #  pos      how many digits placed
    #  tight    still pinned to the bound's prefix
    #  started  a non-zero digit has been placed (drop this if leading zeros are fine)
    #  extra    the problem: a digit mask, a remainder, the previous digit, a count
    if pos == n:
        return 1 if started else 0            # or: return extra, for a sum/tally
    total = 0
    hi = int(bound[pos]) if tight else 9
    for d in range(hi + 1):
        if not started and d == 0:            # still in the leading-zero run
            total += go(pos + 1, tight and d == hi, False, extra)
            continue
        if forbidden(d, extra):               # the problem's own rule
            continue
        total += go(pos + 1, tight and d == hi, True, update(extra, d))
    return total

Range queries need no new machinery. The counter answers $[0, N]$, so:

python

def count_in_range(lo: int, hi: int) -> int:
    return f(hi) - f(lo - 1)        # and f(-1) == 0, so guard lo == 0

Dry run

bound = "325", forbidden digit 4. The columns are the two pictures above, written out. Read free as “how many 3-digit strings so far are already strictly below 325’s prefix and legal”.

position	bound digit	allowed digits below it	free	tight
— (start)	—	—	0	1
0	3	0,1,2 → 3	$0 \times 9 + 1 \times 3 = 3$	1
1	2	0,1 → 2	$3 \times 9 + 1 \times 2 = 29$	1
2	5	0,1,2,3 → 4, not 5	$29 \times 9 + 1 \times 4 = 265$	1

Answer $265 + 1 = 266$.

Three things this trace shows that the code hides:

• The × 9, not × 10. A free prefix has all ten digits available minus the forbidden one. Writing free * 10 is the most common typo and it inflates the answer smoothly — no crash, no obvious pattern, just wrong.
• allowed digits below is not the bound digit. At position 2 the bound digit is 5, but only 4 digits below it are legal, because 4 is excluded. The count of choices and the digit’s value are different quantities that happen to coincide when nothing is forbidden.
• tight stays exactly 1 the whole way, then becomes the answer’s +1. It is counting one thing: the string 325 itself. Check it by hand — there are 326 integers in $[0, 325]$ and 60 of them contain a 4, so $326 - 60 = 266$. Drop the + tight and you get 265, which is off by one only when N itself is legal — the reason this bug survives casual testing. With bound = "440" the tight branch dies at position 0 and the answer, 324, has no +1 in it at all.

Complexity

Let $n =$ len(str(N)) — that is 18 or fewer for any 64-bit bound, which is the point of the whole technique.

Quantity	Cost
States	$n \times 2 \times S$, where $S$ is the extra state’s size
Transitions per state	$10$ (or $B$ in base $B$)
Time	$O(n \cdot S \cdot 10)$
Space	$O(n \cdot S)$ for the memo, $O(n)$ recursion depth
Iterative form	$O(n \cdot S)$ time, $O(S)$ space

Concretely: no forbidden-digit state at all is $\approx 18 \times 2 \times 10 = 360$ steps. A digit mask ($S = 2^{10}$) is $\approx 18 \times 2 \times 1024 \times 10 \approx 3.7 \times 10^5$. A remainder mod $m$ is $S = m$. Everything in this family is microseconds; the only way to make digit DP slow is to put something huge in the extra state, such as the numeric prefix itself.

Why tight is worth almost nothing as a state

tight is true for exactly one path down the recursion at each depth, so it contributes $n$ states in total, not $n \times S$. That is why some templates memoize only the tight is False entries and pass the tight path through uncached — it is correct and saves a little memory. It is also where the memoization bug below comes from.

The variant map

Problem	Extra state	The one thing that changes
No forbidden digit	none	skip d == bad in the loop
LC 233 Number of Digit One	running count of 1s	return the count at pos == n instead of 1, so the DP sums a tally rather than counting strings
LC 357 Count Numbers with Unique Digits	10-bit mask of used digits	skip d if mask >> d & 1; needs started so leading zeros do not consume bit 0
LC 2376 Count Special Integers	10-bit mask	LC 357 with an arbitrary bound instead of $10^n$
LC 1012 Numbers with Repeated Digits	10-bit mask	count the numbers with no repeat, then subtract from N — complement counting is far easier than tracking “has repeated”
LC 600 Non-negative Integers without Consecutive Ones	previous bit	base 2 instead of base 10: hi = bit if tight else 1
LC 788 Rotated Digits	two flags: “all digits rotatable” and “at least one digit changes”	a good number needs both conditions, so two booleans, not one
LC 902 Numbers At Most N Given Digit Set	none	the digit loop iterates the given set, and started handles shorter numbers
Digit sum divisible by k	remainder mod k	update = (rem + d) % k, accept when rem == 0
Range $[L, R]$	—	f(R) - f(L - 1)
Sum, not count	the partial value	return two values per state — the count and the sum — or the sum with the count as a multiplier

Pitfalls

• Dropping the final + tight (recursively: returning 0 instead of 1 at pos == n on the tight path). Off by exactly one, and only when N itself satisfies the property, so half your test cases pass.
• Memoizing across tight. If tight is not part of the cache key, a state computed with the bound capping the position gets reused where the position is unconstrained, and the answer comes out too small. It is a silent undercount, never a crash. Either include tight in the key, or cache only when it is false.
• Leaving the cache alive between calls. On LeetCode the same Solution instance handles many test cases; an lru_cache on a closure over bound is fine, but a self.memo dict keyed only on (pos, tight) returns the previous bound’s answers. Build the cache inside the call, or clear it.
• Confusing tight with started. They are independent: 007 is not tight after two zeros if the bound was 325, but it is also not started. Merging them breaks problems with a digit mask, because the leading zeros consume bit 0 and every answer drops.
• free * 10 instead of free * (number of legal digits) in the iterative form. The tight row is easy to get right and the free row is where the arithmetic hides.
• Building the bound with int arithmetic. N // 10 ** i % 10 works but reverses your mental left-to-right order and produces index bugs. Convert once with str(N) and index forward.
• Counting 0 when the problem says “positive integers”. With leading zeros allowed, the all-zeros string is counted as the number 0. If the problem starts at 1, subtract one or use started.
• Reaching for digit DP when the range is small. For $N \le 10^6$ a for loop with a str() check is three lines and cannot be wrong. Say that out loud in an interview before writing the DP.

Interview follow-ups

They ask	What they’re checking	The answer
“Why is this not exponential?”	Whether you understand tight	Because at every depth exactly one prefix is still pinned to the bound; all the others are interchangeable and collapse into one counted bucket. The branching factor lives in the count, not in the recursion
“Now answer for the range $[L, R]$”	Whether you know the standard reduction	$f(R) - f(L-1)$, where $f$ counts $[0, x]$. Guard $L = 0$, and note the bound is inclusive precisely because of the + tight term
“What if $N$ has 18 digits?”	Whether you spot that nothing changes	Nothing changes — the cost is in len(str(N)), so 18 digits is 18 columns. Take $N$ as a string so you never rely on it fitting in an int
“Give me the sum of the qualifying numbers, not the count”	Whether the state can carry more than a flag	Return a pair per state: the count and the sum. When you prepend digit d at position pos, the sum becomes d * 10^(n-pos-1) * count + sum — the count is needed to place the new digit’s contribution
“Do it in base 2” (LC 600)	Generality	Replace 10 with 2 and str(N) with the binary string. The template is base-agnostic; only hi and the loop range change
“Where would you memoize, and where not?”	Depth of understanding	Cache on (pos, started, extra) and only when not tight — the tight path is a single chain of length $n$, so caching it buys nothing and forgetting to key on it costs correctness
“How do you find the $k$-th such number?”	Whether you can compose techniques	Binary search on the value, using the counter as the predicate: $O(\log N)$ counter calls. Or build the answer digit by digit, subtracting counts as you fix each digit
“Test it”	Engineering judgement	Brute-force the same property for every $N$ up to a few thousand and compare. Digit DP is exactly the kind of code whose bugs are small silent offsets, and a 5-line oracle finds all of them

Practice

7 problems

0 easy2 medium5 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○357Count Numbers with Unique Digitsmedium
• ○788Rotated Digitsmedium
• ○233Number of Digit Onehard
• ○600Non-negative Integers without Consecutive Oneshard
• ○902Numbers At Most N Given Digit Sethard
• ○1012Numbers With Repeated Digitshard
• ○2376Count Special Integershard

Exercises

LC 2376 — Count Special Integers · Hard

pch.exerciseTag pch.exerciseTitle

LC 233 — Number of Digit One · Hard

pch.exerciseTag pch.exerciseTitle

LC 902 — Numbers At Most N Given Digit Set · Hard

pch.exerciseTag pch.exerciseTitle

Self-check

pch.quizTag Digit DP — self-check

1. Why does the tight row of the state machine never hold a count greater than 1?

   A Because the bound is at most 10^18 B Because exactly one prefix of each length can equal the bound's prefix — every other prefix is already strictly below it, and therefore free C Because the memo caps it D It can hold more than 1 on some inputs
   pch.quizShowAnswer

   B — Because exactly one prefix of each length can equal the bound's prefix — every other prefix is already strictly below it, and therefore free — This is the whole technique in one sentence. The branching factor moves into the *count* stored in the free bucket, and the recursion itself stays linear in the number of digits.

2. You omit `tight` from the memo key. What happens?

   A A KeyError B The answer comes out too small, silently — a state computed with the bound capping that position gets reused where the position is unconstrained C The answer comes out too large D Nothing; `tight` is redundant
   pch.quizShowAnswer

   B — The answer comes out too small, silently — a state computed with the bound capping that position gets reused where the position is unconstrained — A tight state has fewer choices available, so its value is smaller. Reusing it for free states undercounts, with no crash and no obvious pattern. Either key on `tight` or cache only when it is false.

3. In the iterative form, a free prefix multiplies by 9 when one digit is forbidden. Why not 10?

   A To leave room for the tight branch B Because a free prefix may extend by any of the ten digits except the forbidden one C Because leading zeros are excluded D Because the bound has 9 digits
   pch.quizShowAnswer

   B — Because a free prefix may extend by any of the ten digits except the forbidden one — The multiplier is the number of *legal* digits, which is a different quantity from the base. Writing 10 inflates the answer smoothly, which makes it a hard typo to notice.

4. Why does the count of [0, 325] end with `+ tight` rather than just the free total?

   A To handle the empty string B Because the surviving tight prefix is the bound itself, and the range is inclusive of N C To fix an off-by-one in the loop D It is optional
   pch.quizShowAnswer

   B — Because the surviving tight prefix is the bound itself, and the range is inclusive of N — 265 free + 1 tight = 266, and 326 − 60 numbers containing a 4 confirms it. Dropping the term is wrong only when N itself qualifies — so the bug passes many test cases. With N = 440 and 4 forbidden, tight is already 0 and the term adds nothing.

5. `tight` and `started` — why are they separate pieces of state?

   A They are the same thing under a different name B They are independent: a prefix of leading zeros is not started, and against a bound like 325 it is also not tight — merging them breaks any problem whose state is a digit mask C `started` only matters in base 2 D `started` is only needed for sums
   pch.quizShowAnswer

   B — They are independent: a prefix of leading zeros is not started, and against a bound like 325 it is also not tight — merging them breaks any problem whose state is a digit mask — If padding zeros are treated as placed digits, they consume bit 0 of a used-digit mask and every number shorter than the bound is rejected. LC 2376 is the standard place this bug shows up.

6. The interviewer changes the bound to N ≤ 10^6. What is the right first move?

   A Write the digit DP anyway — it is asymptotically better B Say that a plain loop over the range with a string check is three lines and cannot be wrong, then offer the digit DP as the version that scales C Refuse; the problem is now trivial D Precompute all answers up to 10^6
   pch.quizShowAnswer

   B — Say that a plain loop over the range with a string check is three lines and cannot be wrong, then offer the digit DP as the version that scales — 10^6 iterations is well inside a second. Naming the simpler correct solution before reaching for the clever one is exactly the judgement the question is testing — and it costs nothing, because you then write the DP anyway.

Recall card

• Cue — count the numbers in a huge range with a digit property; the bound arrives as a string or as $10^{18}$.
• State — (pos, tight, started, extra). tight = still equal to the bound’s prefix, started = a non-zero digit has been placed, extra = the problem (mask, remainder, previous digit, tally).
• Transition — hi = int(bound[pos]) if tight else 9; loop d in 0..hi; the next state is tight only if tight and d == hi.
• Base case — pos == n returns 1 (or extra for a tally), gated on started.
• Cost — $O(n \cdot S \cdot 10)$ with $n \le 18$: always fast unless the extra state is huge.
• Range — f(R) − f(L−1). Inclusive because the tight path counts $N$ itself.
• Two bugs — dropping the tight contribution (off by one, only when N qualifies) and memoizing across tight (silent undercount).

Recap

• Digit DP counts over a range of size $10^{18}$ in the length of the bound, because as you build a number left to right only one prefix is still pinned to the bound and all the rest are interchangeable.
• The state is (pos, tight) plus whatever the specific problem needs. Memorise the skeleton once and the whole family — forbidden digits, unique digits, digit sums, adjacent digits, restricted digit sets — is a two-line edit each.
• started is not tight. Conflating them breaks every mask problem, quietly.
• Ranges are f(R) − f(L−1); sums need the count carried alongside the sum; other bases need only a different hi.
• Verify with a brute-force oracle over small bounds. The failures in this pattern are small silent offsets, not exceptions.

Next: Bitmask and Tree DP — the same “state is not an index” idea, with a subset in the state rather than a digit position.