Digit DP: Counting Numbers with Tight and Started States

1. Introduction and Motivation

A huge family of competitive-programming and interview problems asks a variant of the same question: how many numbers in [L, R] satisfy property P? Property P is usually easy to check for a single number — "digit sum equals 20," "contains no two adjacent equal digits," "does not contain the substring 13," "is divisible by 7." The catch is the range. L and R are often given as plain integers with up to 18 or 19 digits, so $R - L$ can be close to $10^{18}$. Iterating over every value between L and R, checking P on each, is correct but far too slow to finish in any reasonable time.

Digit DP solves this by never enumerating the numbers at all. Instead, it builds a number one digit at a time, from the most significant digit to the least significant, and counts how many ways there are to finish the number so that the final result satisfies P. Because a dynamic-programming state can summarize "everything property P still needs to know" at each digit position, the algorithm explores a state space proportional to the number of digits rather than the magnitude of the numbers themselves.

2. Prerequisites

This lesson assumes the general DP methodology from DSA Part 14: Dynamic Programming Foundations — defining a state, writing a recurrence, and memoizing overlapping subproblems. If you are already comfortable thinking digit-by-digit from bitmask DP, the state-design habits in Bit Manipulation: Core Tricks and Interview Patterns transfer directly to reasoning about digit positions here.

3. Core Insight: Tight and Started States

Suppose you are constructing a number digit-by-digit and want to count how many completions satisfy P, given an upper bound N with digits $N = d_0 d_1 \ldots d_{n-1}$. At each position, the DP state needs exactly two pieces of bookkeeping beyond whatever property P itself requires:

Memoizing on (pos, tight, started, ...) looks like it should be exponential — after all, there are up to $10^{n}$ numbers with $n$ digits. But the DP never stores one entry per number; it stores one entry per state, and the state space is tiny: pos ranges over at most 19 positions (for numbers up to $10^{18}$), tight and started are each one bit, and any extra property-specific dimension (a remaining sum budget, an automaton state, a remainder mod K) is usually small too. Every number that shares the same state from a given position onward has exactly the same number of valid completions, so the DP counts entire equivalence classes of numbers at once instead of counting numbers one by one.

4. A Concrete Example

5. Counting Numbers with Digit Sum Constraints

The example above generalizes directly into a memoized recursion over (pos, tight, remaining), where remaining is the digit-sum budget still allowed. The function below counts integers in [0, N] whose digit sum is at most K; passing K and K - 1 and subtracting gives the count with digit sum exactly K.

from functools import lru_cache

def count_digit_sum_at_most(n, k):
    """Count integers in [0, n] whose decimal digit sum is <= k."""
    if n < 0:
        return 0
    digits = list(map(int, str(n)))
    length = len(digits)

    @lru_cache(maxsize=None)
    def solve(pos, tight, remaining):
        if pos == length:
            return 1
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(0, limit + 1):
            if d > remaining:
                continue  # this digit alone would blow the sum budget
            new_tight = tight and (d == limit)
            total += solve(pos + 1, new_tight, remaining - d)
        return total

    result = solve(0, True, k)
    solve.cache_clear()
    return result

print(count_digit_sum_at_most(25, 5))  # 15

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

long long memo[20][2][200];
bool seen[20][2][200];

long long solve(const std::string& digits, int pos, int tight, int remaining) {
    if (pos == (int)digits.size()) {
        return 1;
    }
    if (seen[pos][tight][remaining]) {
        return memo[pos][tight][remaining];
    }
    int limit = tight ? (digits[pos] - '0') : 9;
    long long total = 0;
    for (int d = 0; d <= limit; ++d) {
        if (d > remaining) continue;  // digit alone exceeds the sum budget
        int newTight = (tight && d == limit) ? 1 : 0;
        total += solve(digits, pos + 1, newTight, remaining - d);
    }
    seen[pos][tight][remaining] = true;
    memo[pos][tight][remaining] = total;
    return total;
}

long long countDigitSumAtMost(long long n, int k) {
    if (n < 0) return 0;
    std::string digits = std::to_string(n);
    std::memset(seen, 0, sizeof(seen));
    return solve(digits, 0, 1, k);
}

int main() {
    std::cout << countDigitSumAtMost(25, 5) << '\n';  // 15
}

public class DigitSumCounter {
    static String digits;
    static long[][][] memo;
    static boolean[][][] seen;

    static long solve(int pos, int tight, int remaining) {
        if (pos == digits.length()) {
            return 1;
        }
        if (seen[pos][tight][remaining]) {
            return memo[pos][tight][remaining];
        }
        int limit = (tight == 1) ? (digits.charAt(pos) - '0') : 9;
        long total = 0;
        for (int d = 0; d <= limit; d++) {
            if (d > remaining) continue;  // digit alone exceeds the sum budget
            int newTight = (tight == 1 && d == limit) ? 1 : 0;
            total += solve(pos + 1, newTight, remaining - d);
        }
        seen[pos][tight][remaining] = true;
        memo[pos][tight][remaining] = total;
        return total;
    }

    static long countDigitSumAtMost(long n, int k) {
        if (n < 0) {
            return 0;
        }
        digits = Long.toString(n);
        memo = new long[20][2][200];
        seen = new boolean[20][2][200];
        return solve(0, 1, k);
    }

    public static void main(String[] args) {
        System.out.println(countDigitSumAtMost(25, 5));  // 15
    }
}

Note that count_digit_sum_at_most counts over [0, N], not [1, N]. Since the number 0 has digit sum 0, it is included whenever K ≥ 0; if you need the count restricted to positive integers, subtract 1 in that case. The function deliberately omits a started flag: a leading zero contributes 0 to the digit sum either way, so tracking it would add a state dimension without changing the answer for this particular property.

6. Counting Numbers with Forbidden Patterns

How many numbers in [0, N] do not contain the digit pattern "13"?

Here the property depends on adjacent digits, so the state needs a small automaton in place of the sum budget: state = 0 means "the previous digit was not 1," and state = 1 means "the previous digit was 1, so a following 3 would complete the forbidden pattern." This is the same idea as a KMP failure function, simplified to the two states this particular two-character pattern needs. Placing a 3 while in state 1 is simply disallowed — that branch contributes nothing further, so the loop skips it instead of recursing into it.

from functools import lru_cache

def count_without_13(n):
    """Count integers in [0, n] whose decimal digits never contain "13"."""
    if n < 0:
        return 0
    digits = list(map(int, str(n)))
    length = len(digits)

    @lru_cache(maxsize=None)
    def solve(pos, tight, state):
        # state 0: previous digit was not 1; state 1: previous digit was 1
        if pos == length:
            return 1
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(0, limit + 1):
            if state == 1 and d == 3:
                continue  # placing 3 here would complete the forbidden "13"
            new_state = 1 if d == 1 else 0
            new_tight = tight and (d == limit)
            total += solve(pos + 1, new_tight, new_state)
        return total

    result = solve(0, True, 0)
    solve.cache_clear()
    return result

print(count_without_13(15))  # 15 (16 numbers in [0,15], only 13 is excluded)

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

long long memoP[20][2][2];
bool seenP[20][2][2];

long long solveP(const std::string& digits, int pos, int tight, int state) {
    if (pos == (int)digits.size()) {
        return 1;
    }
    if (seenP[pos][tight][state]) {
        return memoP[pos][tight][state];
    }
    int limit = tight ? (digits[pos] - '0') : 9;
    long long total = 0;
    for (int d = 0; d <= limit; ++d) {
        if (state == 1 && d == 3) continue;  // would complete forbidden "13"
        int newState = (d == 1) ? 1 : 0;
        int newTight = (tight && d == limit) ? 1 : 0;
        total += solveP(digits, pos + 1, newTight, newState);
    }
    seenP[pos][tight][state] = true;
    memoP[pos][tight][state] = total;
    return total;
}

long long countWithout13(long long n) {
    if (n < 0) return 0;
    std::string digits = std::to_string(n);
    std::memset(seenP, 0, sizeof(seenP));
    return solveP(digits, 0, 1, 0);
}

int main() {
    std::cout << countWithout13(15) << '\n';  // 15
}

public class ForbiddenPatternCounter {
    static String digits;
    static long[][][] memo;
    static boolean[][][] seen;

    static long solve(int pos, int tight, int state) {
        if (pos == digits.length()) {
            return 1;
        }
        if (seen[pos][tight][state]) {
            return memo[pos][tight][state];
        }
        int limit = (tight == 1) ? (digits.charAt(pos) - '0') : 9;
        long total = 0;
        for (int d = 0; d <= limit; d++) {
            if (state == 1 && d == 3) continue;  // would complete forbidden "13"
            int newState = (d == 1) ? 1 : 0;
            int newTight = (tight == 1 && d == limit) ? 1 : 0;
            total += solve(pos + 1, newTight, newState);
        }
        seen[pos][tight][state] = true;
        memo[pos][tight][state] = total;
        return total;
    }

    static long countWithout13(long n) {
        if (n < 0) {
            return 0;
        }
        digits = Long.toString(n);
        memo = new long[20][2][2];
        seen = new boolean[20][2][2];
        return solve(0, 1, 0);
    }

    public static void main(String[] args) {
        System.out.println(countWithout13(15));  // 15
    }
}

As with the digit-sum example, this implementation skips a separate started flag. A leading zero can only push the automaton into state = 0 (zero is neither 1 nor 3), so padding zeros can never spuriously start or complete a match of "13." That is specific to this pattern: a forbidden pattern that itself contains 0, such as "00," would need started to stop padding zeros from being treated as real repeated zeros in the number.

7. Range Counting: Reusing count(N) for [L, R]

This works because [0, R] is the disjoint union of [0, L - 1] and [L, R], so subtracting removes exactly the prefix you don't want. The one subtlety is L - 1 when L = 0: there is no valid number "-1" to build digits from, so count must treat any negative input as an empty range and return 0 immediately, before it tries to convert the number to a digit string. Both functions above already do this with their if n < 0: return 0 guard, so count(R) - count(-1) correctly reduces to just count(R).

Applying this to the worked examples:

# [10, 25] with digit sum <= 5
print(count_digit_sum_at_most(25, 5) - count_digit_sum_at_most(9, 5))  # 15 - 6 = 9

# [10, 25] without the pattern "13" (only 13 itself is excluded)
print(count_without_13(25) - count_without_13(9))  # 25 - 10 = 15

# [0, 25] with digit sum <= 5, written as a range query (L = 0)
print(count_digit_sum_at_most(25, 5) - count_digit_sum_at_most(-1, 5))  # 15 - 0 = 15

The first line matches the worked example directly: of the fifteen numbers in [0, 25] with digit sum ≤ 5, six of them (0–5) fall below 10, leaving nine in [10, 25].

8. Complexity Analysis

Compare that to the naive alternative of checking property P on every integer from L to R, which costs $O(R - L)$ — up to $10^{18}$ checks for the largest ranges this technique is built for. Digit DP replaces a walk over the range with a walk over a state space that only depends on how many digits the numbers have, which is why a range with 19-digit bounds and a modest per-property state size still finishes in a fraction of a second.

9. Applications and Alternatives

When the property doesn't depend on digit order at all (for example, "uses digit 7 at least once, anywhere"), simpler combinatorial counting or inclusion-exclusion can sometimes replace digit DP entirely. Digit DP earns its keep specifically when the property is checked digit-by-digit and the bound N has to be respected exactly, which is exactly the case the tight state exists to handle.

10. Exercises

Easy

1. Count numbers in [1, N] with an even digit sum. (Track just the parity of the sum instead of the full remaining budget.)

Medium

1. Count numbers in [L, R] with no repeated digits. (The extra state is a bitmask of which digits 0–9 have already been used, which also needs started, since a padding zero must not mark digit 0 as "used.")

Hard

1. Count numbers in [L, R] divisible by a given K. Add the running remainder mod K as DP state alongside tight, updating it as (remainder * 10 + d) % K at each digit, and accept only completions that finish with remainder 0. This combines two forms of state tracking in the same recursion: the bound-following tight flag and a property-specific running value.

Review rhythm: tomorrow, rebuild the digit-sum recursion from scratch without notes; next week, implement the divisible-by-K exercise and trace it by hand on a small L, R, K; several weeks later, recognize the same tight/started/automaton state pattern in a new counting problem before reaching for brute force.

11. Summary Cheat Sheet

• Digit DP counts numbers satisfying property P in [0, N] by building digits from most to least significant, without enumerating individual numbers.
• tight tracks whether the digits chosen so far still exactly match N, which caps the next digit choice; once a digit falls strictly below N's digit, later digits are unconstrained.
• started tracks whether a real (non-padding) digit has appeared yet, needed whenever padding zeros could otherwise be miscounted as real digits.
• Extra state dimensions (sum budget, automaton state, remainder mod K) should be exactly as large as the property requires — no larger.
• Range queries reuse count(N) as count(R) - count(L - 1); guard L - 1 = -1 by returning 0 for negative input before touching the number's digits.
• Complexity is $O(\text{digits} \times 2 \times S)$ per query, versus $O(R - L)$ for brute-force enumeration.