Digit Dynamic Programming: Counting Numbers with Constraints in [L, R] Ranges

Evaluating the frequency of integers within an interval $[L, R]$ that satisfy intricate positional, parity, or arithmetic digit constraints is a classic challenge in algorithmic problem solving. When $R$ reaches $10^{18}$, brute-force iteration over individual numbers is impossible. Digit Dynamic Programming (Digit DP) addresses this by processing numbers digit-by-digit from most significant to least significant, reducing an intractable $O(R - L)$ search to an optimal $O(D \cdot B \cdot |S|)$ dynamic program, where $D$ is the digit length, $B$ is the numerical base, and $|S|$ is the problem-specific state space.

Prefix Subtraction and the Range Query Paradigm

Directly counting valid integers in an arbitrary bounded range $[L, R]$ introduces dual boundary constraints at every digit position, complicating the recursive state logic. We simplify the problem by leveraging the principle of prefix subtraction:

$$\text{count}([L, R]) = f(R) - f(L - 1)$$

where $f(N)$ computes the total number of valid integers in the semi-closed interval $[0, N]$ (or $[1, N]$ depending on zero-handling rules). By transforming the two-ended range query into two independent single-bounded queries anchored at $0$, the algorithm only needs to enforce an upper bound restriction during digit generation.

The Canonical Digit DP State Tuple

The standard Digit DP algorithm constructs numbers through a depth-first search (DFS) with memoization. The recursive state is formalized as a four-component tuple: (index, is_tight, is_leading_zero, state).

1. Index Dimension (index)

Represents the current digit position being decided, moving from the most significant digit ($index = 0$) down to the least significant digit ($index = D - 1$). The base case occurs when $index = D$, at which point all digits have been placed, and the function returns 1 if the accumulated state satisfies the acceptance condition, or 0 otherwise.

2. The Tight Boundary Constraint (is_tight)

A boolean flag indicating whether the prefix generated so far matches the exact prefix of the upper bound $N$:

• If is_tight == true: The current digit choice is strictly bounded above by the corresponding digit in $N$, denoted $N[index]$. Selecting any digit $d \in [0, N[index] - 1]$ releases the tight constraint for all subsequent positions (the prefix is now strictly smaller than $N$'s prefix), transitioning to next_tight = false. Selecting $d = N[index]$ keeps the constraint active, transitioning to next_tight = true.
• If is_tight == false: The generated prefix is already strictly smaller than $N$'s prefix. The current digit can be chosen freely from $[0, B - 1]$ (e.g. $[0, 9]$ in base-10), and subsequent states remain unconstrained (next_tight = false).

3. Leading Zeros Flag (is_leading_zero)

A boolean flag tracking whether any non-zero digit has been placed yet. This distinction is vital for problems where the digit 0 carries semantic meaning (such as counting the frequency of the digit 0, checking adjacent digit differences, or calculating digit products):

• While placing leading zeros ($d = 0$ and is_leading_zero == true), the number has not formally started. The number 007 represents the single-digit integer 7, not a three-digit integer with two zeros.
• Placing any non-zero digit $d > 0$ transitions the flag to next_leading_zero = false for all remaining digits.

4. Auxiliary Accumulator (state)

The problem-specific context accumulated by the prefix. Common examples include:

• Sum of Digits: Tracking $\sum d_i \pmod K$ or the raw sum for sum-of-digit constraints.
• Bitmask of Present Digits: An integer mask $\text{mask} \in [0, 2^{10} - 1]$ tracking which distinct digits have appeared.
• Previous Digit: The value of the immediately preceding digit for monotonic or non-repeating digit constraints.

Memoization Mechanics: Why We Cache Unconstrained Branches

A frequent error among practitioners is improperly sizing or corrupting the memoization table by storing results across all boolean configurations. In canonical Digit DP, the memoization table memo[index][state] is indexed solely by index and state, omitting is_tight and is_leading_zero:

$$\text{memo}[index][state] = \text{valid suffixes from position } index \text{ with context } state$$

Why is this mathematically sound? Because when is_tight == false and is_leading_zero == false, the set of valid suffix completions from position index onwards depends strictly on the current state, completely independent of the specific prefix digits chosen to reach it. Conversely, when is_tight == true, that specific branch is traversed at most once per solve call, rendering caching unnecessary. By restricting memoization reads and writes to !is_tight && !is_leading_zero, we minimize memory consumption while maximizing cache hit rates.

Complete C++ Reference Implementation

The following self-contained implementation demonstrates Digit DP to solve a classic competitive programming problem: Count how many integers in $[L, R]$ have a digit sum divisible by $K$ and contain no adjacent identical digits.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

class DigitDPSolver {
private:
    int K;
    vector<int> digits;
    // memo[index][sum_mod_k][prev_digit]
    // index: 0..19, sum_mod_k: 0..K-1, prev_digit: 0..9 (10 represents 'none')
    long long memo[20][100][11];

    long long dfs(int idx, bool is_tight, bool is_leading_zero, int sum_mod, int prev_digit) {
        // Base case: all digits placed
        if (idx == (int)digits.size()) {
            // Valid if non-empty number and sum is divisible by K
            return (!is_leading_zero && sum_mod == 0) ? 1 : 0;
        }

        // Memoization lookup: only when unconstrained and leading zeros resolved
        if (!is_tight && !is_leading_zero && memo[idx][sum_mod][prev_digit] != -1) {
            return memo[idx][sum_mod][prev_digit];
        }

        int limit = is_tight ? digits[idx] : 9;
        long long total = 0;

        for (int d = 0; d <= limit; ++d) {
            bool next_tight = is_tight && (d == limit);
            bool next_lz = is_leading_zero && (d == 0);

            if (next_lz) {
                // Still placing leading zeros; no adjacent constraint applies
                total += dfs(idx + 1, next_tight, true, 0, 10);
            } else {
                // Skip if current digit matches previous digit (adjacent constraint)
                if (!is_leading_zero && d == prev_digit) continue;

                int next_sum_mod = (sum_mod + d) % K;
                total += dfs(idx + 1, next_tight, false, next_sum_mod, d);
            }
        }

        if (!is_tight && !is_leading_zero) {
            memo[idx][sum_mod][prev_digit] = total;
        }
        return total;
    }

    long long countUpTo(long long n) {
        if (n < 0) return 0;
        if (n == 0) return 0; // If 0 is not considered a valid natural number

        digits.clear();
        string s = to_string(n);
        for (char c : s) digits.push_back(c - '0');

        // Clear memoization table before each upper bound evaluation
        memset(memo, -1, sizeof(memo));
        return dfs(0, true, true, 0, 10);
    }

public:
    DigitDPSolver(int divisor) : K(divisor) {}

    long long countRange(long long L, long long R) {
        return countUpTo(R) - countUpTo(L - 1);
    }
};

Common State Pattern Variations

Digit DP adapts to diverse combinatorial properties by modifying the state space:

Subtle Pitfalls and Debugging Strategies

Even experienced algorithm designers encounter edge-case failures when deploying Digit DP. The following checklist identifies the most common sources of error:

• State Table Cache Pollution: If a problem queries multiple ranges $[L_1, R_1], [L_2, R_2], \dots$ with varying parameter values (such as varying $K$), failing to memset the memoization table between queries leaks state answers from prior instances.
• Zero Representation Ambiguity: Clarify whether the number $0$ is considered valid under the problem definition. In problems requiring non-zero digit products, $0$ will either invalidate the condition or trivially satisfy it, altering whether $L = 0$ requires explicit compensation.
• Integer Base Generalization: For problems framed in binary or hexadecimal, ensure the branching loop iterates up to $B - 1$ (e.g. $d \in [0, 1]$ in base-2), and that string parsing extracts digits according to the intended radix.

Frequently Asked Questions

Below are authoritative answers to common inquiries regarding Digit Dynamic Programming implementation and theory:

Why is the memoization table in Digit DP typically indexed only by (index, state) and not by tight or leading_zero?

When is_tight is true, the allowable digit choices are strictly constrained by the upper bound's prefix, meaning that specific state branch is visited at most once per solve call. When is_leading_zero is true, leading zeros alter the numerical semantics. Once is_tight and is_leading_zero are both false, the number of valid suffixes depends solely on the remaining digit index and the cumulative state, making that result universal and safely reusable across all unconstrained prefixes.

How does prefix subtraction handle the lower bound L when L equals zero?

The prefix formula $\text{count}([L, R]) = f(R) - f(L - 1)$ breaks down if $L = 0$ because $L - 1 = -1$ is undefined. To resolve this, evaluate $f(R)$ directly for $L = 0$, or compute $f(R) - f(L - 1)$ only for $L \ge 1$ and explicitly check if $0$ satisfies the predicate when $L = 0$.

Can Digit DP be applied to bases other than decimal base-10?

Yes. Digit DP generalizes directly to any integer base $B \ge 2$. The upper limit when unconstrained becomes $B - 1$ instead of $9$, and the number is decomposed into its base-$B$ positional digits. This is widely used in binary (base-2) bit-counting and popcount problems.

What is the typical time and space complexity of a Digit DP solution?

For a number with $D$ digits, a branching factor $B$ (usually 10 for decimal), and a state space of size $|S|$, the total number of distinct states is $D \cdot |S|$. Each state performs at most $B$ transitions, yielding an overall time complexity of $O(D \cdot B \cdot |S|)$ and space complexity of $O(D \cdot |S|)$.