Digit DP

At a glance

The instinct

You cannot loop to 10^18. But numbers are just strings of at most 19 digits, and a property like "no repeated digit" or "digit sum divisible by k" only needs a summary of the digits already placed. So fill the digits left to right. While your prefix equals N's prefix you are tight: the next digit cannot exceed N's digit. The moment you place a smaller digit you are free: every remaining position can be 0-9, and all those free branches with the same summary have identical answers - memoise them.

Ranges are handled by subtraction: count(L..R) = f(R) - f(L - 1).

Recognise it

Not this pattern if...

• You need to construct the next/previous number with a property (often greedy, e.g. Next Greater Element III).
• The property depends on the value as a whole in a non-local way you cannot summarise (e.g. primality of the number).
• n is small enough (≤ 10^6) to just loop and check - do that first and mention digit DP as the scalable version.

Memory hack

Analogy: filling in a combination lock that must not exceed a target code. While every wheel so far equals the target, the next wheel is capped. Once one wheel is lower, the rest of the wheels spin freely - and every free spin of "3 wheels left, same history" behaves the same, so you count it once.

DP framing:

• State - (pos, summary, tight, started); summary is the problem-specific memory (used-digit mask, digit sum mod k, previous digit, count of ones).
• Choice - the digit placed at pos: 0 .. (tight ? N[pos] : 9), possibly restricted to an allowed set.
• Base case - at pos == len, return 1 if the built number is valid (or the collected statistic for sum-type problems).
• Order - most significant digit first; memoise only the free (non-tight) states.

Say it out loud in the interview:

1. "I count numbers ≤ N, then answer ranges with f(R) - f(L-1)."
2. "Walking digits from the left, I track tight, leading-zero, and this summary: ..."
3. "Only non-tight states are memoised, so the table is positions × summaries."

How it works

For N = 325 the recursion tree branches like this:

flowchart TD
    S["pos 0, tight, limit 3"] --> A["digit 0..2: free"]
    S --> B["digit 3: still tight"]
    A --> A2["remaining 2 positions: 0..9 each, memoised"]
    B --> C["pos 1, tight, limit 2"]
    C --> C1["digit 0..1: free"]
    C --> C2["digit 2: still tight"]
    C2 --> D["pos 2, tight, limit 5: digits 0..5"]

Only one path ever stays tight (it spells N itself), so almost all work happens in free states, and there are just positions × summaries of those. Leading zeros matter whenever zero is "special": the number 7 written as 007 must not count as using digit 0 three times, so a started flag says whether a non-zero digit has been placed yet.

Java template

class DigitDp {
    private char[] d;
    private Long[][] memo;                       // memo[pos][state] for free, started states
    private static final int STATES = 1 << 10;   // problem-specific: here a used-digit mask

    long countUpTo(long n) {
        if (n < 0) return 0;
        d = Long.toString(n).toCharArray();
        memo = new Long[d.length][STATES];       // reset: pos meaning depends on N's length
        return dfs(0, 0, true, false);
    }

    long countRange(long lo, long hi) { return countUpTo(hi) - countUpTo(lo - 1); }

    private long dfs(int pos, int state, boolean tight, boolean started) {
        if (pos == d.length) return started && accept(state) ? 1 : 0; // the number 0 is excluded
        if (!tight && started && memo[pos][state] != null) return memo[pos][state];
        int limit = tight ? d[pos] - '0' : 9;
        long res = 0;
        for (int dig = 0; dig <= limit; dig++) {
            boolean nowStarted = started || dig != 0;
            if (nowStarted && !allowed(state, dig)) continue;
            int next = nowStarted ? step(state, dig) : state;          // leading zeros change nothing
            res += dfs(pos + 1, next, tight && dig == limit, nowStarted);
        }
        if (!tight && started) memo[pos][state] = res;
        return res;
    }

    // Problem-specific hooks (shown: all digits distinct).
    private boolean allowed(int mask, int dig) { return (mask & (1 << dig)) == 0; }
    private int step(int mask, int dig) { return mask | (1 << dig); }
    private boolean accept(int mask) { return true; }
}

class DigitStatistic {
    private char[] d;
    private Integer[][] memo;

    // Sum-type digit DP: total count of digit 1 over all numbers in [0, n].
    int countDigitOne(int n) {
        d = Integer.toString(n).toCharArray();
        memo = new Integer[d.length][d.length + 1];
        return dfs(0, 0, true);
    }

    private int dfs(int pos, int ones, boolean tight) {
        if (pos == d.length) return ones;                  // each finished number contributes its ones
        if (!tight && memo[pos][ones] != null) return memo[pos][ones];
        int limit = tight ? d[pos] - '0' : 9, res = 0;
        for (int dig = 0; dig <= limit; dig++) {
            res += dfs(pos + 1, ones + (dig == 1 ? 1 : 0), tight && dig == limit);
        }
        if (!tight) memo[pos][ones] = res;
        return res;
    }
}

Complexity

• Time: O(len × S × B) - positions × summary states × digit choices (B = 10 for decimal, 2 for binary). The tight chain adds only O(len × B).
• Space: O(len × S) for the memo plus O(len) recursion depth.
• With a used-digit mask (S = 1024) and 10 positions that is about 10^5 operations - instant.

Variations

• Filter count - count numbers whose digits pass a test. Count Numbers with Unique Digits, Count Special Integers.
• Aggregate statistic - return a sum instead of 0/1. Number of Digit One, total digit sum over a range.
• Restricted digit set - iterate only over allowed digits; numbers shorter than N are counted with |set|^k and only full-length numbers need the tight walk. Numbers At Most N Given Digit Set.
• Remainder / sum state - digit sum mod k, or value mod k. Count of Integers (digit sum within bounds).
• Binary digits - same idea in base 2 with "previous bit" state. Non-negative Integers without Consecutive Ones.
• Two bounds at once - carry tightLow and tightHigh flags instead of subtracting, handy when L - 1 is awkward (string inputs).

Common mistakes

• Treating leading zeros as real digits, so 7 looks like "007" and fails a "distinct digits" check.
• Forgetting the edges of f(R) - f(L - 1): L = 0, and whether 0 itself should be counted.
• Reusing a memo indexed by pos (from the left) across two different N lengths - reset it, or index by digits remaining.
• Overflowing int when counts approach 10^18; use long or the required modulus.
• Writing limit = 9 when the problem restricts digits, or forgetting the restricted set when tight.

All practice problems

3 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.