Digit DP

Digit DP

Some problems ask you to count the numbers in a range that satisfy a property of their digits: how many numbers up to 10¹⁸ have a digit sum divisible by 7, contain no digit 4, have all distinct digits, and so on. Checking each number one by one is hopeless for ranges that large. Digit DP builds the numbers one digit at a time, from the most significant digit, and counts all valid completions at once. It's usually O(number of digits × a small state × 10).

Two ideas make it work

1. Count up to N, then subtract

Almost every problem is phrased as a range [lo, hi]. Solve the easier question "how many valid numbers in [0, N]?" and combine:

count(lo, hi) = f(hi) − f(lo − 1)

2. The tight flag

Write N as a digit string, for example N = 3 5 2. While building a number digit by digit, you must not exceed N. Whether you're constrained depends on the digits chosen so far:

• If every digit so far equals N's digit at the same position, you're tight: the next digit may be at most N's next digit.
• As soon as you place a smaller digit than N's at some position, the number is already below N, whatever follows. From then on you're free, and any digit 0–9 is allowed.

N = 352
first digit 3 (tight)  → second digit may be 0..5
first digit 2 (free)   → second digit may be 0..9, since 2xx < 352 already

That's the whole trick. The state is (position, tight, whatever the property needs). When not tight, the count of completions depends only on the position and the property state, not on the digits chosen before. That's what makes memoization pay off.

A template: count numbers in [0, N] whose digit sum is divisible by k

class DigitSumCounter {
    private char[] digits;
    private int k;
    private Long[][] memo;                         // [position][sum mod k], used only when NOT tight

    long count(long n, int k) {                    // how many x in [0, n] have digitSum(x) % k == 0
        if (n < 0) return 0;
        this.digits = Long.toString(n).toCharArray();
        this.k = k;
        this.memo = new Long[digits.length][k];
        return go(0, 0, true);
    }

    private long go(int pos, int sumMod, boolean tight) {
        if (pos == digits.length) return sumMod == 0 ? 1 : 0;        // a complete number
        if (!tight && memo[pos][sumMod] != null) return memo[pos][sumMod];

        int limit = tight ? digits[pos] - '0' : 9;
        long total = 0;
        for (int d = 0; d <= limit; d++) {
            total += go(pos + 1, (sumMod + d) % k, tight && d == limit);
        }
        if (!tight) memo[pos][sumMod] = total;
        return total;
    }
}
// answer for [lo, hi]: count(hi, k) − count(lo − 1, k)

Notes on the details:

• Numbers shorter than N are counted naturally, as if padded with leading zeros: 42 is built as 0-4-2 when N has three digits. Leading zeros don't change a digit sum, so this is harmless here.
• Only non-tight states are memoized. There's exactly one tight path (it follows N's own digits), so caching it saves nothing, and tight results depend on N's remaining digits, which the key doesn't capture.
• Complexity: positions (≤ 19 for long) × states (k) × 10 digits, which is tiny even for N = 10¹⁸.

When leading zeros matter: a started flag

For properties like "all digits distinct" or "no two adjacent digits equal", leading zeros are not real digits. The number 7 must not be treated as 0-0-7 with a repeated 0. Add a started flag that stays false until the first non-zero digit is placed:

// Count numbers in [1, N] whose digits are all distinct
class DistinctDigits {
    private char[] digits;
    private Long[][] memo;                          // [position][used-digit mask], when !tight && started

    long count(long n) {
        if (n <= 0) return 0;
        digits = Long.toString(n).toCharArray();
        memo = new Long[digits.length][1 << 10];
        return go(0, 0, true, false);
    }

    private long go(int pos, int mask, boolean tight, boolean started) {
        if (pos == digits.length) return started ? 1 : 0;        // "all zeros" is not a positive number
        if (!tight && started && memo[pos][mask] != null) return memo[pos][mask];

        int limit = tight ? digits[pos] - '0' : 9;
        long total = 0;
        for (int d = 0; d <= limit; d++) {
            boolean nowStarted = started || d != 0;
            if (nowStarted && (mask & (1 << d)) != 0) continue;   // digit already used
            int nextMask = nowStarted ? mask | (1 << d) : mask;   // leading zeros don't consume "0"
            total += go(pos + 1, nextMask, tight && d == limit, nowStarted);
        }
        if (!tight && started) memo[pos][mask] = total;
        return total;
    }
}

The bitmask records which digits 0–9 have been used. There are 2¹⁰ possible masks, so the state space is at most 19 × 1024, still small.

More examples of the property state

For "numbers whose value is divisible by m and whose digit sum is divisible by m", you carry both remainders. The state is the product of the two, which is still small for small m.

How to recognise digit DP

• The range is huge (up to 10⁹ … 10¹⁸), so iterating over numbers is impossible.
• The condition depends on the digits (sum, pattern, set of digits, divisibility).
• You're asked to count (or sum) matching numbers, not to list them.

Follow-up questions this topic invites — and their answers

Q: What does the tight flag mean? A: That every digit placed so far equals N's corresponding digit, so the next digit is capped at N's digit at this position. Once any smaller digit is placed, the number is already below N, and all later digits are unrestricted.

Q: Why memoize only when not tight? A: Only one path is tight (the one following N's own digits), so its states are never revisited. A tight state's answer also depends on N's remaining digits, which aren't part of the memo key. Non-tight states with the same position and property state always have the same answer.

Q: How do you handle a range [lo, hi]? A: Compute f(hi) − f(lo − 1), where f(x) counts valid numbers in [0, x] (or [1, x]). Be careful when lo is 0, and with whether 0 itself counts as valid.

Q: When do leading zeros need special handling? A: When the property looks at the digit sequence itself: distinct digits, adjacent-digit rules, "contains digit 0". Padding zeros would otherwise be counted as real digits. A started flag separates padding from real digits. For properties unaffected by extra zeros, like digit sums and divisibility, padding is harmless.

Q: What's the complexity? A: O(D × S × 10), where D is the number of digits (about 19 for 64-bit numbers), S is the number of distinct property states (sum values, remainders, masks), and 10 is the digit choices per position. It's typically microseconds, even for N = 10¹⁸.