Lab 11 — Digit DP

Goal

Count integers in [0, N] (and [L, R] by subtraction) that satisfy a per-digit property, in O(digits × states × 10). Master the canonical recursion dp(pos, tight, state, leading_zero) and apply it to LeetCode 902, 2719, and the hard classic LeetCode 1012. After this lab you should write a digit-DP template from a cold start in <15 minutes and adapt its state to a new property in <5.

Background Concepts

Digit DP builds the number one decimal position at a time, left to right, counting how many completions satisfy the property. The four canonical parameters:

pos — index into the digits of N, 0 = most significant.
tight — are we still bounded by N’s prefix? If True, the current digit may not exceed N[pos]; if it equals N[pos] we stay tight, otherwise we go loose. Loose stays loose forever.
state — everything the property needs to remember (a used-digit bitmask, a running remainder mod k, a “previous digit,” a digit-sum, …).
leading_zero — are we still in the leading-zero region? A leading zero is not a real digit: it must not mark the mask, must not count as “used digit 0,” and often must not start counting a length.

Why tight collapses the exponential tree. Only one prefix of the search tree is ever tight — the one equal to N’s prefix. Every loose branch is fully free and its subtree count depends only on (pos, state), so it memoizes. The tight branch is a single spine of length = len(N). That is why the whole thing is polynomial: the state space is pos × state × {tight} × {leading}, and tight/leading each multiply by at most 2.

Answering [L, R]. Count is monotone and prefix-summable: answer(L, R) = f(R) − f(L − 1), where f(X) counts valid numbers in [0, X]. Handle L = 0 by defining f(−1) = 0.

Leading-zero pitfalls. For properties about which digits are used, 00007 uses only the digit 7, not 0 — so while leading_zero is True, a chosen 0 must recurse without touching the mask. Get this wrong and you overcount (e.g., treating short numbers as if padded with real zeros).

Interview Context

Digit DP is the sledgehammer for “how many numbers up to N have property P.” Candidates who haven’t seen it try to iterate [0, N] (10⁹+ — TLE) or hand-roll fragile combinatorics that break on the tight boundary. Recognizing the pattern and producing the memoized dp(pos, tight, state, leading) cleanly — especially the leading-zero and complement-counting subtleties — is a strong L5 signal. The tell: N up to 10⁹ or 10¹⁸ and “count numbers such that …”.

Problem Statement (LC 902)

Given an array digits of sorted distinct decimal digit characters (a subset of 1..9) and a positive integer n, count how many positive integers can be written using digits from digits (with repetition, any length) that are less than or equal to n. The main implementation showcase in this lab is the harder sibling, LC 1012 (Numbers With Repeated Digits), which exercises every subtlety — bitmask state, leading zeros, and complement counting.

Constraints

1 ≤ digits.length ≤ 9, digits distinct and sorted, each in 1..9 (LC 902).
1 ≤ n ≤ 10⁹ (LC 902); 1 ≤ N ≤ 10⁹ (LC 1012). Technique scales to 10¹⁸ with 64-bit ints.

Clarifying Questions

Is the range inclusive of N? (Yes — f counts [0, N].)
Do we count 0 itself? (LC 1012 counts positives [1, N]; the DP naturally produces the count including 0, so subtract or start at 1.)
Are leading zeros part of the number? (No — 007 is the number 7; leading zeros mark nothing.)
For “repeated digit,” does a single-digit number ever count? (No — one digit cannot repeat.)
Is the property about the value (mod k, digit-sum) or about the set of digits used? (Determines whether state is a remainder/sum or a bitmask.)
For [L, R], is L possibly 0? (If so, f(L − 1) = f(−1) = 0.)

Examples

LC 1012  N = 20   → 1     (only 11 has a repeated digit)
LC 1012  N = 100  → 10    (11,22,…,99,100)
LC 1012  N = 1000 → 262

LC 902   digits=[1,3,5,7], n=100        → 20   (4 one-digit + 16 two-digit)
LC 902   digits=[1,4,9],   n=1000000000 → 29523

Initial Brute Force

Loop x from 0 to N, convert each to a string, test the property (len(set(str(x))) < len(str(x)) for repeated digits), and count. Correct and trivial to write — use it as the oracle.

Brute Force Complexity

O(N × D) where D = number of digits (the per-number string work). At N = 10⁹ that is ~10¹⁰ character operations — TLE by orders of magnitude. The whole point of digit DP is to replace the N factor with len(N) ≈ log₁₀ N.

Optimization Path

Replace the linear scan with the position-by-position count. Direct counting has D positions, each with 2 values of tight, 2 of leading, and at most 2^10 mask states (for the used-digits property) or k remainder states — times 10 transitions. That is O(D × states × 10): for LC 1012, 10 × 2 × 2 × 1024 × 10 ≈ 4×10⁵ — instant.

Complement counting is the key trick for “repeated digit”: counting numbers with a repeat directly is awkward, but counting numbers with all-distinct digits is a clean bitmask DP. Then repeated = N − distinct. Always look for the easier complement.

Final Expected Approach

Count all-distinct-digit numbers in [1, N] with a memoized dp(pos, mask, tight, leading); the answer to LC 1012 is N − that. The [L, R] wrapper subtracts two f calls. LC 902 is the same template with a digit-set filter and no mask.

from functools import lru_cache

def count_distinct(N):
    """Count x in [1, N] with pairwise-distinct decimal digits."""
    if N < 1:
        return 0
    s = list(map(int, str(N)))
    n = len(s)

    @lru_cache(maxsize=None)                 # nested def ⇒ cache is per-call
    def dp(pos, mask, tight, leading):
        if pos == n:
            return 0 if leading else 1       # all-zeros path is the integer 0
        hi = s[pos] if tight else 9
        total = 0
        for d in range(hi + 1):
            nt = tight and d == hi
            if leading and d == 0:
                total += dp(pos + 1, mask, nt, True)      # 0 marks nothing yet
            elif (mask >> d) & 1:
                continue                                   # digit d already used
            else:
                total += dp(pos + 1, mask | (1 << d), nt, False)
        return total

    ans = dp(0, 0, True, True)
    dp.cache_clear()                          # tight/leading are per-N: never persist
    return ans

def num_dup_digits_at_most_n(N):              # LC 1012, via complement
    return N - count_distinct(N)

def distinct_in_range(L, R):                  # [L, R] = f(R) − f(L−1)
    return count_distinct(R) - count_distinct(L - 1)

def at_most_n_given_digit_set(digits, N):     # LC 902, same template, no mask
    s = str(N)
    n = len(s)
    D = sorted(int(c) for c in digits)

    @lru_cache(maxsize=None)
    def dp(pos, tight):
        if pos == n:
            return 1
        total = 0
        hi = int(s[pos])
        for d in D:
            if tight and d > hi:
                break
            total += dp(pos + 1, tight and d == hi)
        return total

    shorter = sum(len(D) ** k for k in range(1, n))   # all 1..n−1 digit numbers
    ans = shorter + dp(0, True)
    dp.cache_clear()
    return ans

Data Structures Used

The digit list of N (list(map(int, str(N)))) as the positional bound.
functools.lru_cache keyed on (pos, mask, tight, leading) for memoization.
A bitmask (1 << d) as the used-digit state for LC 1012; a remainder or digit-sum scalar for other properties.

Correctness Argument

Positional decomposition. Every integer in [0, N] has a unique decimal representation read left to right; the DP enumerates each exactly once by fixing digits position by position. tight guarantees the tight spine never emits a number exceeding N, and once loose, all remaining positions range freely 0..9 — so the union of tight-spine and loose-subtree completions is exactly [0, N].

Leading-zero handling. While leading holds, a chosen 0 recurses without touching mask and keeps leading = True, so 00007 reaches the base case having marked only digit 7 — it is counted as the number 7 with a one-element digit set, never as “using digit 0.” The base case returns 0 for the all-leading path so the empty number isn’t miscounted as a positive.

Complement. distinct + repeated = N over [1, N] (partition by whether any digit repeats), so repeated = N − distinct; the DP computes distinct exactly, hence LC 1012 is exact.

Complexity

Quantity	Value
States	pos (≈10) × mask (≤1024) × tight (2) × leading (2)
Transitions	×10 digits
Time	O(digits × states × 10) — ~10⁵ for LC 1012
Space	O(states) for the cache

Implementation Requirements

Memoize with a nested dp and call dp.cache_clear() (or use a fresh lru_cache per N) — see the caching pitfall below.
Handle leading_zero separately from tight; they are independent booleans.
For [L, R], always compute f(R) − f(L − 1), defining f(x) = 0 for x < 0.
Prefer complement counting when the target property is messy and its negation is clean.

Tests

LC 1012: N = 20 → 1, N = 100 → 10, N = 1000 → 262.
Exhaustive: for every N in 1..1999, num_dup_digits_at_most_n(N) equals the brute-force count.
[L, R] wrapper vs brute force on random 1 ≤ L ≤ R ≤ 3000.
LC 902: ([1,3,5,7], 100) → 20, ([1,4,9], 10⁹) → 29523.
Edge: N = 9 (all single-digit ⇒ 0 repeats); N = 10 (still 0); N = 11 (first repeat).

Follow-up Questions

Why must tight (and leading) not persist across different N? Their meaning depends on N’s specific digits, so a cache entry (pos, mask, tight=True, …) computed for one N is wrong for another. The nested-def + cache_clear() (or a per-call lru_cache) resets the cache each call. The truly N-independent entries are the loose ones (tight=False), which is exactly why loose subtrees memoize within a single call.
How do leading zeros interact with a “digits used” property? A leading 0 must not set bit 0 of the mask, because 007 uses no zero. So the transition keeps leading=True and leaves mask untouched on a chosen 0; only the first nonzero digit flips leading off and starts marking. Conflating the two overcounts short numbers as zero-padded.
How do you do digit DP in another base — e.g., count numbers ≤ N with no two consecutive 1-bits (LC 600)? Same recursion over the binary digits of N: state = “was the previous bit 1,” transition skips d=1 when the previous was 1. pos runs over ~30 bits instead of ~10 decimal digits.
How do you handle a sum-type query — sum of digit-sums over [L, R], not just a count? Carry an aggregate pair (count, total) up the recursion. On appending digit d to count completions contributing total, the parent gets count more numbers and total + d × count added digit-sum. Combine children by summing both components.
How do you count numbers divisible by k in a range? Add remainder mod k to state; the transition updates (rem × 10 + d) % k, and the base case counts only rem == 0. State size grows by a factor of k.
What is LC 2719 (Count of Integers) and how does it fit? Count integers in [num1, num2] whose digit-sum lies in [min_sum, max_sum]. state is the running digit-sum (capped at max_sum), and [L, R] is the f(num2) − f(num1 − 1) wrapper — a textbook sum-in-range digit DP.

Product Extension

Analytics and fraud systems that bucket over huge id/amount ranges use digit-DP-style counting to answer “how many account numbers in this block match a structural rule” without materializing the range. Lexicographic/odometer generation (next-valid-code, license-plate or coupon-code counting under alphabet constraints) is digit DP over a custom alphabet. Query optimizers estimating “how many keys in [lo, hi] satisfy a predicate on their digits” reuse the same positional counting. Anywhere the range is astronomically large but the property is per-digit, digit DP replaces enumeration.

Language/Runtime Follow-ups

Python: functools.lru_cache on a nested def is the cleanest memo; call cache_clear() between Ns. Big ints are free, so 10¹⁸ needs no special handling.
Java: use an explicit Integer[][][][] memo (or long), and reset it per call; -1 sentinel for “unvisited.” Beware int overflow on counts — use long.
C++: vector or a fixed long long dp[20][1<<10][2][2] with a visited flag; pass the digit array by reference. Reset between test cases.
Go: 4-D slice memo built per call; Go has no memo decorator, so wire it manually. Use int64 for counts.
JS/TS: Map keyed on a serialized pos,mask,tight,leading string, or nested arrays; BigInt only if counts exceed 2⁵³.

Common Bugs

Persisting tight across N in a shared cache: a cache reused between f(R) and f(L−1) with tight in the key returns stale counts. Clear the cache per call or key it correctly.
Leading zero marks the mask: treating a leading 0 as “used digit 0” undercounts distinct-digit numbers (every short number wrongly conflicts on 0). Skip the mask while leading.
Counting the number 0 as positive: the all-leading path must return 0, not 1, or f is off by one and LC 1012’s complement is wrong.
hi not clamped by tight: iterating d to 9 on a tight branch emits numbers > N. hi = s[pos] if tight else 9.
nt = tight and d == hi computed with the wrong hi: if you loosen hi to 9 first, d == hi no longer detects the boundary. Compute nt against s[pos] on tight branches.
Off-by-one in [L, R]: using f(R) − f(L) instead of f(R) − f(L − 1) drops L itself.

Debugging Strategy

Run the DP against the brute-force oracle for every N in 1..2000 — a single mismatch pinpoints the boundary or leading-zero bug by its smallest failing N. If it first fails at a power of 10 (100, 1000), suspect the tight-boundary or length-transition logic. If it fails at repdigit-adjacent values (11, 22, 100), suspect the mask/leading interaction. Instrument dp to print (pos, mask, tight, leading) → return on the smallest failing N and compare against a hand trace of the two-digit case.

Mastery Criteria

Wrote the dp(pos, tight, state, leading) template from cold in <15 minutes.
Solved LC 1012 via complement counting with a distinct-digit bitmask.
Adapted state to a new property (mod k, digit-sum, no-consecutive-ones) in <5 minutes.
Explained why tight collapses the tree to polynomial and why it must not persist across N.
Handled leading zeros correctly for a “digits used” property.
Built the [L, R] = f(R) − f(L − 1) wrapper without an off-by-one.

LeetCode Interview — Extreme Coding