What is Digit Dynamic Programming (Digit DP)?
Learn digit DP for counting numbers up to N with digit properties, including the tight flag and a Python example.
Expected Interview Answer
Digit DP is a dynamic programming technique for counting or summarizing numbers within a range (like 1 to N) that satisfy a digit-based property — such as “digit sum equals k” or “no two adjacent digits are equal” — by processing the number one digit at a time from most significant to least significant while tracking a small state, instead of iterating through every number individually.
The state typically includes the current digit position, whether the number built so far is still “tight” (equal to N’s prefix, which restricts which digits can come next) or already strictly less (free to place any digit), and problem-specific accumulators like a running digit sum, remainder mod k, or count of a particular digit pattern seen so far. At each position, the DP tries every valid next digit (0-9, or fewer if tight), recursing into the next position with an updated tight flag and updated accumulator, and memoizes on (position, tight, accumulator) since many different prefixes collapse into the same state. This turns a problem that would naively require iterating up to N (which could be 10^18) into one that runs in roughly O(digits * accumulator_range * 10), independent of N’s actual magnitude. Digit DP is the standard tool whenever a problem asks “how many numbers up to N satisfy property P” and P can be checked digit by digit with bounded extra state.
- Counts numbers up to N in O(digits) instead of O(N)
- Handles N as large as 10^18 efficiently
- The tight flag correctly enforces the upper bound digit by digit
- Generalizes to sums, counts, and range queries via subtraction (f(N) - f(M-1))
AI Mentor Explanation
A scorer counting how many possible innings scorecards up to a maximum total exist, satisfying some rule like “no single over gave more than 6 runs,” builds the scorecard over by over instead of listing every possible full scorecard individually. At each over the scorer tracks whether the partial total is still exactly capped by the maximum (“tight”, meaning future overs are restricted) or already safely under it (free to add any valid over score). By remembering just the over number, the tight flag, and any running total needed for the rule, wildly different partial scorecards that reach the same state get counted together instead of enumerated separately. This digit-by-digit — or here, over-by-over — construction with a small remembered state is exactly the trick that avoids listing every possible scorecard by hand.
Step-by-Step Explanation
Step 1
Convert N to a digit array
Represent the upper bound N as a list of digits, most significant first, to process one digit at a time.
Step 2
Define the state
State = (position, tight flag, problem-specific accumulator like digit sum or remainder mod k).
Step 3
Recurse over valid digits
At each position, try digits 0 through (9 if not tight, else N’s digit at that position); update tight and the accumulator for the recursive call.
Step 4
Memoize non-tight states
Cache results keyed by (position, accumulator) once tight is false, since those states are reused across many different prefixes.
What Interviewer Expects
- Explain the role of the tight flag and why it restricts allowed digits
- State why only non-tight states can be memoized (tight states depend on N’s exact prefix)
- Give a canonical example: count numbers up to N with a given digit sum, or count numbers divisible by k
- Explain how to handle a range [L, R] via f(R) - f(L-1)
Common Mistakes
- Attempting to memoize tight states, which are not reusable since they depend on N’s specific prefix
- Forgetting to handle leading zeros correctly when the problem cares about actual digit count
- Iterating N numbers one by one instead of building digit DP, missing the whole point of the technique for large N
- Not resetting the tight flag correctly when a chosen digit is strictly less than N’s digit at that position
Best Answer (HR Friendly)
“Digit DP is how I count numbers up to some huge limit that satisfy a rule about their digits, without actually looping through every number one by one. I build the number digit by digit, keeping track of whether I am still bound by the upper limit’s digits or already free to choose anything, plus whatever small extra info the rule needs, like a running digit sum.”
Code Example
from functools import lru_cache
def count_with_digit_sum(n, target):
digits = list(map(int, str(n)))
@lru_cache(maxsize=None)
def solve(pos, remaining_sum, tight, started):
if remaining_sum < 0:
return 0
if pos == len(digits):
return 1 if (started and remaining_sum == 0) else 0
limit = digits[pos] if tight else 9
total = 0
for d in range(0, limit + 1):
new_tight = tight and (d == limit)
new_started = started or d > 0
new_sum = remaining_sum - d if new_started else remaining_sum
total += solve(pos + 1, new_sum, new_tight, new_started)
return total
return solve(0, target, True, False)Follow-up Questions
- How would you extend this to count numbers in a range [L, R] instead of 1 to N?
- Why can only non-tight states be safely memoized?
- How would you adapt digit DP to count numbers divisible by k instead of matching a digit sum?
- How does digit DP’s time complexity compare to brute-force iteration for N up to 10^18?
MCQ Practice
1. What does the “tight” flag track in digit DP?
Tight means the number built so far equals N’s prefix exactly, so the next digit is capped at N’s digit at that position; if not tight, any digit 0-9 is allowed.
2. Why can digit DP states only be memoized when tight is false?
A tight state’s future behavior is uniquely determined by N’s remaining digits at that position, so it is only ever reached by one specific prefix, making caching pointless; non-tight states are reachable from many different prefixes and represent the same reusable subproblem.
3. What is the primary benefit of digit DP over brute-force iteration for counting numbers up to N satisfying a digit property?
Digit DP processes O(log N) digit positions with a bounded accumulator range, making it efficient even for N as large as 10^18, versus brute-force iterating every number up to N.
Flash Cards
What does the tight flag mean in digit DP? — The digits chosen so far exactly match N’s prefix, so the next digit is capped at N’s corresponding digit.
Why are non-tight states memoizable but tight states are not? — Non-tight states are reached from many different prefixes and represent the same reusable subproblem; tight states are unique to N’s specific digit sequence.
What is digit DP’s rough time complexity? — O(digits * accumulator_range * 10), independent of N’s actual size.
How do you count a range [L, R] with digit DP? — Compute f(R) - f(L-1), where f(x) counts qualifying numbers from 1 (or 0) to x.