⚙️AlgorithmIntermediate

Digit DP

Key Points

  • •
    Digit DP is a dynamic programming technique for counting or aggregating values over all integers in a range that satisfy a digit-based property.
  • •
    It builds numbers from the most significant digit to the least, carrying a 'tight' flag to respect the upper bound and a 'leading zeros' flag to avoid false contributions.
  • •
    The core state is typically dp[pos][tight][leading][state], where 'state' encodes your property (e.g., sum so far, remainder modulo m, previous digit, or a digit-used mask).
  • •
    To answer a range query [L, R], compute F(R) − F(L − 1), where F(x) is the DP result over [0, x].
  • •
    Transitions iterate over the next digit d from 0 to (tight ? boun : 9) and update the state accordingly.
  • •
    Time complexity is roughly O(numbe_digits × stat × 10), which is practical for up to 10^18 with careful state design.
  • •
    Handle leading zeros carefully: they should not trigger constraints like 'digit used' or 'adjacent equal' until the first nonzero digit appears.
  • •
    Digit DP is versatile: it can count valid numbers, compute sums like sum of digits over a range, or enforce constraints like divisibility, uniqueness, or adjacency conditions.

Prerequisites

  • →Dynamic Programming (DP) fundamentals — Digit DP builds on the idea of overlapping subproblems and memoization.
  • →Base representation of integers — Understanding how numbers decompose into digits is core to designing states and transitions.
  • →Recursion and memoization — Typical implementations are top-down recursive with memoized states.
  • →Modular arithmetic — Many tasks involve remainders (divisibility) or require modulo to prevent overflow.
  • →Time and space complexity analysis — To design feasible states and predict performance for constraints like 10^18.
  • →Bitmasking — Digit uniqueness or subset constraints are naturally represented as bitmasks.
  • →Handling edge cases — Correctly accounting for leading zeros and whether to include the number 0 is crucial.

Detailed Explanation

Tap terms for definitions

01Overview

Digit DP is an algorithmic pattern designed to answer questions about numbers by looking at their digits one by one. Instead of checking every number in a range, which would be too slow, we build numbers digit-by-digit under constraints (like 'no digit 7', 'sum of digits ≤ S', 'no adjacent equal digits'). The trick is to add a 'tight' flag that tells us whether we have already matched the bound's prefix exactly; if so, the next digit is limited to the bound's corresponding digit, otherwise it can be anything from 0 to 9. Another important flag is 'leading zeros', which indicates whether we have started the number yet; constraints should usually ignore leading zeros. You can think of Digit DP as a layered decision process: at each position pos, we choose a digit and move to pos + 1, updating any necessary 'state', like the current remainder modulo m or which digits we've used. We cache (memoize) results for each state so we do not recompute the same subproblem, giving excellent performance even for 19-digit numbers (up to 10^18). The final result for a range [L, R] comes from computing F(R) − F(L − 1), where F(x) summarizes valid numbers from 0 to x. This approach is extremely flexible and turns many 'count numbers with property P in a range' problems into manageable dynamic programs.

02Intuition & Analogies

Imagine you are filling out a form with 19 boxes for digits (enough for numbers up to 10^18). You start at the leftmost box and must obey two rules: (1) at every step, if you have matched the upper bound so far, the next digit cannot exceed the corresponding digit of the bound; (2) you have not 'started' placing a real number until you place the first nonzero digit—leading zeros don't count as real digits for most constraints. Now suppose you're told 'never write the digit 7.' As you go box by box, you just avoid 7. If you’re also told 'the number must be divisible by 13', you carry along the current remainder as you write each digit (like a running checksum). Or if you’re told 'no two adjacent digits can be the same', you remember the last digit you wrote and avoid writing it again next. Because many different paths through these boxes share the same situation—same position, same tightness to the bound, same started/leading-zeros status, and the same extra info (like remainder or previous digit)—you can reuse (memoize) results. This is like remembering that from a certain partially filled form, there are X valid completions no matter how you got there. That reuse is what makes Digit DP fast. Finally, to handle a range [L, R] rather than only an upper bound R, you compute the number of valid forms up to R and subtract those up to L − 1. This cancels out everything below L, leaving exactly the count in [L, R].

03Formal Definition

Let x be a nonnegative integer with decimal representation ... , where is the most significant digit. Define a function F(x) that aggregates (counts or sums) over all integers y in [0, x] that satisfy a digit-local property P. We construct a DP over positions with state variables capturing whether the prefix equals the bound and relevant information for P. A common DP state is f(pos, tight, leading, s), where pos ∈ [0, n] is the next index to fill, tight ∈ {0, 1} indicates whether the prefix equals the bound's prefix, leading ∈ {0, 1} indicates whether all previously placed digits were 0, and s encodes property-specific information (e.g., remainder modulo m, previous digit, or a bitmask of used digits). The transition chooses the next digit d from 0 to hi, where if , otherwise 9. The new state updates to pos + 1, tight' = tight ∧ ( when ), leading' = leading ∧ (), and s' = Update(s, d, leading). The base case at returns an aggregate value depending on whether the formed number (possibly 0) satisfies P. For range queries [L, R], the answer is F(R) − F(L − 1). The total complexity is typically O(n × × 10), where n is the number of digits of x and is the size of the property-specific state space.

04When to Use

Use Digit DP when the constraint depends on the decimal (or base-b) digits rather than on the whole integer arithmetically in a nonlocal way. Typical uses include: forbidding certain digits; bounding the sum of digits; controlling adjacency (e.g., no equal neighbors); divisibility by tracking remainder modulo m; and uniqueness via a bitmask of used digits. It is especially effective when the upper bound is large (like up to 10^18), making brute force impossible. Digit DP shines when you need to evaluate many valid completions of a prefix under a tight upper bound, and when the property can be updated locally with each digit placed. It also works well for aggregation beyond counting, such as summing digit sums or weighted values across the valid numbers, by returning structured values (e.g., pairs: count and sum) from the DP. Avoid Digit DP when the property is not digit-local or requires global factors not captured by a compact state—e.g., primality of the whole number without additional optimizations, or constraints that require looking ahead arbitrarily far beyond what a finite state can track. Similarly, it is suboptimal if the base is extremely large or the state space explodes beyond manageable size.

⚠️Common Mistakes

  1. Mishandling leading zeros: Constraints like 'digit used' or 'adjacent equal' should ignore leading zeros. Keep a 'leading' flag and only apply rules once you place the first nonzero digit. 2) Forgetting the range trick: Always compute Answer([L, R]) = F(R) − F(L − 1). Off-by-one errors here are common; explicitly handle L = 0 (then L − 1 = −1 yields F(−1) = 0).
  2. Wrong tight update: The next state's tight flag is not simply whether tight was 1; it becomes tight' = (tight == 1 and d == bound_digit_at_pos). 4) Not resetting memoization between different bounds or parameters: The DP cache depends on the bound’s digits and on parameters like m; rebuild or clear memo whenever those change.
  3. Overflow: Counts up to 10^18 fit in 64-bit signed integers, but aggregated sums (e.g., sum of digits over all numbers up to 10^18) can exceed 64-bit. Use modular arithmetic or wider types appropriately. 6) Counting zero incorrectly: Decide whether '0' should be counted for your property. If your base case excludes 'started = false', you might miss counting 0 when it should be included (e.g., divisible by m). Handle 0 explicitly when needed.
  4. State explosion: Adding too many dimensions can make the DP slow or memory-heavy. Strive for minimal sufficient state (e.g., use prev digit index 0..9 plus a sentinel 10, or a compact 10-bit mask). 8) Mixing properties without adjusting transitions: When combining properties (e.g., remainder and uniqueness), ensure each transition correctly updates every component of the composite state.

Key Formulas

Range Decomposition

Explanation: To count/aggregate over a range [L, R], compute the cumulative result up to R and subtract the cumulative result up to L − 1. Handle L = 0 by defining F(-1) = 0.

Digit DP Recurrence

Explanation: The value at a state equals the sum over all allowed next digits up to hi (either 9 or the bound's digit, depending on tight). Each digit updates the flags and the property state.

Digit Bound

Explanation: When we have matched the bound so far (tight = 1), the next digit cannot exceed the bound's digit at that position; otherwise any digit 0..9 is allowed.

Remainder Transition

Explanation: When still in leading zeros, placing another zero does not change the numeric value and keeps remainder the same; otherwise update the remainder as usual.

Time Complexity

Explanation: We consider n digit positions, about 10 transitions per state, and a property-specific state space of size |S|. This is efficient even for n up to 19.

Space Complexity (Memoized)

Explanation: Storing memo for each pos, tight (2), leading (2), and property state |S| yields linear space in n times the state space size.

Positional Value

Explanation: The value of a number built from digits is the sum of each digit times its positional base power. Digit DP exploits this positional structure.

Branch Factor

Explanation: At each step, we branch over digits 0..hi. The maximum branching per state is 10 (digits 0 through 9).

Complexity Analysis

Let n be the number of digits of the upper bound (for 64-bit x, ). A generic Digit DP state has dimensions: position (n), tight (2), leading (2), and a property-specific state space of size (e.g., m for remainder modulo m, 10 for a previous-digit constraint, or 2^{10} for digit-uniqueness). Each state tries up to 10 digits. Therefore the time complexity is O(n × × 10), which in practice is about a few million operations even for = 2^{10} = 1024. This is easily feasible under typical contest time limits. Space complexity for top-down memoization is O(n × × 2 × 2) to store answers for each combination of indices. For example, with a remainder state , the memo size is approximately 19 × 1000 × 4 ≈ 76,000 entries, which is lightweight. With a bitmask state = 1024, the memo is about 19 × 1024 × 4 ≈ 77,824 entries; still small. If you add more state dimensions (e.g., both remainder and mask), the multiplicative blow-up can become significant, so balance expressiveness and feasibility. Note that drastically reduces branching near the most significant digits because many digits get pruned by the upper bound. Also, memoization eliminates repeated work over many paths that converge to the same state. When aggregating values like sums, the arithmetic per transition may include constant-time operations (additions, multiplications, modulo), keeping the per-edge cost O(1). Hence overall complexity remains O(n × × 10) time and O(n × ) space.

Code Examples

Count numbers in [L, R] that do NOT contain digit 7
1#include <bits/stdc++.h>
2using namespace std;
3
4// Digit DP: count numbers in [0, x] with no digit 7.
5// We'll use dp[pos][tight][leading] memoization.
6
7struct No7DP {
8    string s;                    // digits of bound x
9    long long dp[20][2][2];      // -1 means uncomputed
10
11    long long dfs(int pos, int tight, int leading) {
12        if (pos == (int)s.size()) {
13            // We've formed a number (possibly 0). It's valid because we never allowed digit 7.
14            return 1; // counts this number
15        }
16        long long &res = dp[pos][tight][leading];
17        if (res != -1) return res;
18        res = 0;
19        int hi = tight ? (s[pos] - '0') : 9;
20        for (int d = 0; d <= hi; ++d) {
21            if (d == 7) continue; // forbid digit 7 anywhere (including first nonzero)
22            int nextTight = tight && (d == hi);
23            int nextLeading = leading && (d == 0);
24            res += dfs(pos + 1, nextTight, nextLeading);
25        }
26        return res;
27    }
28
29    long long solve(long long x) {
30        if (x < 0) return 0; // empty set
31        s = to_string(x);
32        memset(dp, -1, sizeof(dp));
33        return dfs(0, 1, 1);
34    }
35};
36
37long long count_range(long long L, long long R) {
38    No7DP solver;
39    return solver.solve(R) - solver.solve(L - 1);
40}
41
42int main() {
43    ios::sync_with_stdio(false);
44    cin.tie(nullptr);
45
46    long long L, R;
47    // Example input: L R
48    // e.g., 1 1000
49    if (!(cin >> L >> R)) return 0;
50    cout << count_range(L, R) << "\n";
51    return 0;
52}
53

We count all numbers up to x that avoid digit 7 by recursively placing digits from most significant to least significant. The tight flag ensures we never exceed x, and the leading flag allows leading zeros. Since we always skip d = 7, the base case returns 1 for any completed number (including 0). The final range answer is solve(R) − solve(L − 1).

Time: O(n × 10), with n ≤ 19 for 64-bit xSpace: O(n × 2 × 2) for memoization
Count numbers in [L, R] divisible by m (handling leading zeros and zero separately)
1#include <bits/stdc++.h>
2using namespace std;
3
4// Digit DP: count numbers in [0, x] that are divisible by m.
5// We do not count the number 0 inside the DP (started==false) to avoid accidental inclusion;
6// we'll add it manually if needed (i.e., if 0 in range and 0 % m == 0 which is always true).
7
8struct DivisibleDP {
9    string s;
10    int m;
11    // dp[pos][tight][leading][rem] = count
12    vector<vector<vector<vector<long long>>>> dp;
13
14    long long dfs(int pos, int tight, int leading, int rem) {
15        if (pos == (int)s.size()) {
16            // Valid if we've actually formed a number (not all leading zeros) and remainder is 0.
17            return (!leading && rem == 0) ? 1LL : 0LL;
18        }
19        long long &res = dp[pos][tight][leading][rem];
20        if (res != -1) return res;
21        res = 0;
22        int hi = tight ? (s[pos] - '0') : 9;
23        for (int d = 0; d <= hi; ++d) {
24            int nextTight = tight && (d == hi);
25            int nextLeading = leading && (d == 0);
26            int nextRem = rem;
27            if (!nextLeading) {
28                // If we've started (i.e., not all zeros), update remainder with this digit
29                nextRem = ( (leading ? 0 : rem) * 10 + d ) % m; // works either way
30            }
31            res += dfs(pos + 1, nextTight, nextLeading, nextRem);
32        }
33        return res;
34    }
35
36    long long solve(long long x, int mod) {
37        if (x < 0) return 0;
38        m = mod;
39        s = to_string(x);
40        dp.assign(s.size(), vector<vector<vector<long long>>>(2, vector<vector<long long>>(2, vector<long long>(m, -1))));
41        return dfs(0, 1, 1, 0);
42    }
43};
44
45long long count_divisible_in_range(long long L, long long R, int m) {
46    DivisibleDP solver;
47    long long res = solver.solve(R, m) - solver.solve(L - 1, m);
48    // Include 0 explicitly if it's in [L, R]
49    if (L <= 0 && 0 <= R) res += 1; // 0 is divisible by m
50    return res;
51}
52
53int main() {
54    ios::sync_with_stdio(false);
55    cin.tie(nullptr);
56
57    long long L, R; int m;
58    // Example input: L R m
59    // e.g., 1 1000000 13
60    if (!(cin >> L >> R >> m)) return 0;
61    cout << count_divisible_in_range(L, R, m) << "\n";
62    return 0;
63}
64

We track the remainder modulo m as part of the state. Leading zeros are treated specially: while still leading, placing 0 does not update the remainder. The base case counts only numbers that have started (not all zeros) and have remainder 0. We then add 0 separately if the interval includes it.

Time: O(n × m × 10)Space: O(n × m × 2 × 2)
Sum of digits over [L, R] modulo 1e9+7 using an aggregator Digit DP
1#include <bits/stdc++.h>
2using namespace std;
3
4// Compute Sum_{x in [L,R]} sum_of_digits(x) modulo MOD via Digit DP aggregator.
5// The DP returns a pair {count, sum} for [0, bound]. We include 0 naturally (count=1, sum=0 at base).
6
7static const long long MOD = 1000000007LL;
8
9struct Node { long long cnt, sum; }; // both modulo MOD
10
11struct SumDigitsDP {
12    string s;
13    Node dp[20][2][2];
14    bool vis[20][2][2];
15
16    Node add(Node a, Node b) {
17        return Node{ (a.cnt + b.cnt) % MOD, (a.sum + b.sum) % MOD };
18    }
19
20    Node dfs(int pos, int tight, int leading) {
21        if (pos == (int)s.size()) {
22            // One completed number (including 0); sum of digits contributes 0 here
23            return Node{1, 0};
24        }
25        if (vis[pos][tight][leading]) return dp[pos][tight][leading];
26        vis[pos][tight][leading] = true;
27        Node res{0, 0};
28        int hi = tight ? (s[pos] - '0') : 9;
29        for (int d = 0; d <= hi; ++d) {
30            int nextTight = tight && (d == hi);
31            int nextLeading = leading && (d == 0);
32            Node child = dfs(pos + 1, nextTight, nextLeading);
33            // If not leading (we have started) or d != 0 starts the number, the placed digit contributes d * (#numbers formed by the rest)
34            if (!nextLeading) {
35                // We placed a real digit at this position; its contribution repeats for all completions of the suffix
36                child.sum = (child.sum + (child.cnt * d) % MOD) % MOD;
37            }
38            res = add(res, child);
39        }
40        return dp[pos][tight][leading] = res;
41    }
42
43    long long solve(long long x) {
44        if (x < 0) return 0;
45        s = to_string(x);
46        memset(vis, 0, sizeof(vis));
47        Node ans = dfs(0, 1, 1);
48        return ans.sum % MOD;
49    }
50};
51
52long long sum_digits_range(long long L, long long R) {
53    SumDigitsDP solver;
54    long long res = (solver.solve(R) - solver.solve(L - 1)) % MOD;
55    if (res < 0) res += MOD;
56    return res;
57}
58
59int main() {
60    ios::sync_with_stdio(false);
61    cin.tie(nullptr);
62
63    long long L, R;
64    // Example input: L R
65    // e.g., 0 1000000000000000000
66    if (!(cin >> L >> R)) return 0;
67    cout << sum_digits_range(L, R) << "\n";
68    return 0;
69}
70

This aggregator DP returns both the count of completions and the sum of digits over all completions. When adding a digit d at position pos, that digit contributes d times the number of ways to fill the suffix. We use modulo arithmetic to avoid overflow and include 0 by returning {1, 0} at the base case.

Time: O(n × 10)Space: O(n × 2 × 2)
Count numbers in [L, R] with no two adjacent equal digits
1#include <bits/stdc++.h>
2using namespace std;
3
4// Digit DP: count numbers in [0, x] with no two adjacent equal digits.
5// State adds 'prev' digit (0..9) and a sentinel 10 for 'no previous yet'.
6
7struct NoAdjacentEqualDP {
8    string s;
9    long long dp[20][2][2][11]; // pos, tight, leading, prev(0..10)
10
11    long long dfs(int pos, int tight, int leading, int prev) {
12        if (pos == (int)s.size()) {
13            // We count 1 for every formed number, including 0. A single-digit 0 trivially has no adjacent equals.
14            return 1;
15        }
16        long long &res = dp[pos][tight][leading][prev];
17        if (res != -1) return res;
18        res = 0;
19        int hi = tight ? (s[pos] - '0') : 9;
20        for (int d = 0; d <= hi; ++d) {
21            int nextTight = tight && (d == hi);
22            int nextLeading = leading && (d == 0);
23            int nextPrev = prev;
24            if (!nextLeading) {
25                // We're placing a real digit
26                if (leading) {
27                    // First real digit; no adjacency check yet
28                    nextPrev = d;
29                } else {
30                    if (d == prev) continue; // violates 'no adjacent equal'
31                    nextPrev = d;
32                }
33            } else {
34                // Still leading zeros; keep prev as sentinel 10
35                nextPrev = 10;
36            }
37            res += dfs(pos + 1, nextTight, nextLeading, nextPrev);
38        }
39        return res;
40    }
41
42    long long solve(long long x) {
43        if (x < 0) return 0;
44        s = to_string(x);
45        for (int i = 0; i < 20; ++i)
46            for (int a = 0; a < 2; ++a)
47                for (int b = 0; b < 2; ++b)
48                    for (int c = 0; c < 11; ++c)
49                        dp[i][a][b][c] = -1;
50        return dfs(0, 1, 1, 10); // 10 = sentinel for 'no previous'
51    }
52};
53
54long long count_no_adjacent_equal_in_range(long long L, long long R) {
55    NoAdjacentEqualDP solver;
56    return solver.solve(R) - solver.solve(L - 1);
57}
58
59int main() {
60    ios::sync_with_stdio(false);
61    cin.tie(nullptr);
62
63    long long L, R;
64    // Example input: L R
65    // e.g., 1 1000
66    if (!(cin >> L >> R)) return 0;
67    cout << count_no_adjacent_equal_in_range(L, R) << "\n";
68    return 0;
69}
70

We keep track of the previous placed digit (prev) with a sentinel 10 meaning 'none yet'. While still in leading zeros, we do not apply the adjacency constraint. Once started, we reject any transition where the new digit equals prev. The DP counts 0 as valid; the range difference handles [L, R].

Time: O(n × 11 × 10) ≈ O(n × 110)Space: O(n × 2 × 2 × 11)