Digit DP

Here is a problem that looks simple at first: how many integers between 1 and N have a digit sum equal to S? If N is small, say up to a million, you can just iterate through every number, add up its digits, and check. But what if N is up to $10^{18}$? You cannot iterate through a quintillion numbers. Brute force is dead on arrival.

This is where digit DP comes in. Instead of iterating through every number in the range, you construct valid numbers one digit at a time, from left to right, using dynamic programming to avoid redundant work. The result is an algorithm whose runtime depends on the number of digits in N (at most 18 for $10^{18}$), not on N itself. A problem that looks intractable becomes almost trivial.

Building numbers digit by digit

The core idea is to think of a number not as a single value but as a sequence of digits. The number 235 is really the sequence [2, 3, 5]. To count how many numbers up to 235 satisfy some property, we build candidate numbers one digit at a time, starting from the most significant digit (the leftmost one).

At each position, we choose a digit to place. But we cannot just place any digit we want. We need to make sure the number we are building does not exceed N. This is where the tight constraint comes in.

The tight flag

Suppose N = 235 and we are building a 3-digit number. For the first digit, we can place 0, 1, or 2. If we place 0 or 1, then for the remaining digits we are completely free: any digit from 0 to 9 is fine, because a number starting with 0xx or 1xx is guaranteed to be at most 235. But if we place 2 (matching N's first digit), we are "tight": the second digit can only go up to 3, not 9, or we might exceed 235.

This is the tight flag. When tight = True, the digit at the current position is bounded by the corresponding digit of N. When tight = False, we have already placed a smaller digit at some earlier position, so the rest can be anything from 0 to 9. The tight constraint propagates: if we are tight and we place a digit equal to N's digit at this position, we stay tight for the next position. If we place anything smaller, the tight constraint drops and never comes back.

A concrete walkthrough

Let us count how many numbers from 0 to 235 have a digit sum of exactly 5. We process the digits [2, 3, 5] from left to right, tracking (position, tight, digit_sum_so_far).

At position 0 (hundreds digit), with tight = True, we can place 0, 1, or 2.

• Place 0: tight becomes False. We need the remaining two digits to sum to 5. Since we are no longer tight, each of the remaining digits can be 0-9. We need to count pairs (d1, d2) with d1 + d2 = 5 and 0 <= d1, d2 <= 9. That gives us 6 pairs: (0,5), (1,4), (2,3), (3,2), (4,1), (5,0).
• Place 1: tight becomes False. Remaining digits must sum to 4. Pairs: (0,4), (1,3), (2,2), (3,1), (4,0), which is 5.
• Place 2: tight stays True. Remaining digits must sum to 3, and the tens digit is bounded by 3.

Following the tight branch further, at position 1 with tight = True, digits must sum to 3, limit is 3:

• Place 0: tight drops. Units digit must be 3. One way.
• Place 1: tight drops. Units digit must be 2. One way.
• Place 2: tight drops. Units digit must be 1. One way.
• Place 3: tight stays. Units digit must be 0, and is bounded by 5. Place 0. One way.

That branch gives us 4. Total: 6 + 5 + 4 = 15 numbers from 0 to 235 with digit sum 5.

The beauty is that we never enumerated all 236 numbers. We worked through at most 3 positions with at most 10 choices each, and the memoization handled the overlapping subproblems.

The memoization state

The state for digit DP is always a tuple: (position, tight, ...problem-specific state). The position tells us which digit we are filling. The tight flag tells us whether we are still constrained by N. The problem-specific state depends on the question being asked:

• Digit sum equals S: state is the running digit sum.
• No repeated digits: state is a bitmask of digits already used.
• Divisible by K: state is the running remainder modulo K.
• No two adjacent digits the same: state is the last digit placed.

The position ranges from 0 to D (the number of digits). The tight flag is boolean. The problem-specific state has its own range. The total number of DP states is $D \times 2 \times |\text{state space}|$, and at each state we try at most 10 digits. This is why digit DP is polynomial: even though N itself might be astronomically large, the number of distinct DP states is small.

Handling leading zeros

Some problems need special care with leading zeros. For example, if you are counting numbers with no repeated digits, the number 007 should not count the 0s as "used" digits, otherwise you would wrongly conclude that 70 has a repeated digit.

The fix is to add a started flag to the state. It is False until we place the first nonzero digit. While started is False, we do not update the problem-specific state (we skip the zeros). Once we place a nonzero digit, started becomes True and stays True.

@lru_cache(maxsize=None)
def dp(pos, tight, started, state):
    if pos == n:
        return 1 if started and is_valid(state) else 0
    limit = digits[pos] if tight else 9
    res = 0
    for d in range(0, limit + 1):
        new_tight = tight and d == limit
        if not started and d == 0:
            res += dp(pos + 1, new_tight, False, state)
        else:
            res += dp(pos + 1, new_tight, True, update(state, d))
    return res

Not every problem needs this flag. If the constraint is purely about digit sums, leading zeros contribute 0 to the sum and do not cause issues. But for constraints involving digit identity (repeated digits, specific digit patterns), the started flag is essential.

Range queries: f(R) - f(L-1)

Most problems ask you to count numbers in a range [L, R], not [0, N]. The standard trick is to define f(N) as the count of valid numbers in [0, N], then compute f(R) - f(L-1). This works because digit DP naturally counts from 0 up to N. The subtraction removes everything below L.

Be careful with off-by-one errors. If L = 0, then L-1 = -1, which has no digits. Handle this edge case explicitly (usually f(-1) = 0).

The code template

Here is a general-purpose digit DP template that handles most problems:

from functools import lru_cache

def count(num_str):
    digits = list(map(int, num_str))
    n = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos, tight, state):
        if pos == n:
            return 1 if is_valid(state) else 0
        limit = digits[pos] if tight else 9
        res = 0
        for d in range(0, limit + 1):
            new_tight = tight and d == limit
            new_state = transition(state, d)
            res += dp(pos + 1, new_tight, new_state)
        return res

    return dp(0, True, initial_state)

You plug in three things: initial_state (the starting value of your problem-specific state), transition(state, d) (how the state updates when you place digit d), and is_valid(state) (whether the final state represents a valid number). For the digit-sum-equals-S problem, initial_state = 0, transition(state, d) = state + d, and is_valid(state) = (state == S).

Common variants

Digit sum constraints. The state is the running sum. If you want digit sum equal to S, check at the end. If you want digit sum at most S, you can prune early: if the running sum already exceeds S, stop recursing.

No repeated digits. The state is a bitmask of the 10 possible digits (0-9), so the state space is $2^{10}$ = 1024. Before placing digit d, check if bit d is already set in the mask. This is one of the cases where the started flag matters: you do not want to mark 0 as "used" while still in the leading-zero phase.

Divisibility by K. The state is the current number modulo K. The transition is new_state = (state * 10 + d) % K. At the end, check if the state is 0. The state space is K, so the total complexity is $O(D \cdot 2 \cdot K \cdot 10)$.

Digit pattern constraints. Some problems forbid certain digit sequences (e.g., no two consecutive digits the same, or no digit 4 followed by digit 7). The state is the last digit placed, giving a state space of 10. The transition checks whether placing d after the last digit violates the constraint.

Why the complexity is polynomial

The magic of digit DP is the gap between the range of numbers (up to $10^{18}$) and the number of DP states (polynomial in the number of digits). A number up to $10^{18}$ has at most 19 digits. With the digit-sum variant where S can be up to 162 ($9 \times 18$), the state space is $19 \times 2 \times 163$ = about 6,200 states, each requiring a loop of 10 iterations. That is roughly 62,000 operations to search through a quintillion numbers.

This dramatic compression happens because the DP exploits the structure of the problem. It does not care which specific digits were placed at earlier positions. It only cares about the summary captured by the state. Two different partial numbers that have the same position, tight flag, and running digit sum will have exactly the same count of valid completions. Memoization ensures we compute each such count only once.

Full Example: Numbers At Most N Given Digit Set

LeetCode 902. Numbers At Most N Given Digit Set asks: given an array of digits (like ["1", "3", "5", "7"]) and a number N, count how many positive integers can be formed using only those digits that are less than or equal to N.

This is digit DP in its purest form. The "state" is trivially empty: there is no running sum or bitmask to track, just the tight constraint. The only question at each position is: which digits from the allowed set can I place here without exceeding N?

def atMostNGivenDigitSet(digits, n):
    s = str(n)
    num_digits = len(s)
    d = len(digits)
    total = 0

    # Count all numbers with fewer digits than N
    # A k-digit number has d choices per position
    for k in range(1, num_digits):
        total += d ** k

    # Count numbers with exactly num_digits digits (digit DP with tight)
    for i, ch in enumerate(s):
        # How many allowed digits are strictly less than ch?
        less = sum(1 for dig in digits if dig < ch)
        total += less * (d ** (num_digits - i - 1))

        # If ch itself is in the digit set, stay tight and continue
        if ch not in digits:
            break
    else:
        # We never broke out, so N itself is a valid number
        total += 1

    return total

Walkthrough: digits = ["1", "3", "5", "7"], N = 100

N has 3 digits. First, count numbers with fewer digits:

• 1-digit: $4^1 = 4$ numbers (1, 3, 5, 7)
• 2-digit: $4^2 = 16$ numbers (11, 13, 15, ..., 77)

Total so far: 20.

Now count 3-digit numbers ≤ 100. Process digit by digit:

• Position 0: N's digit is '1'. Allowed digits less than '1': none. So 0 numbers start with a smaller digit. Is '1' in the set? Yes, so continue tight.
• Position 1: N's digit is '0'. Allowed digits less than '0': none. Is '0' in the set? No. Break.

No 3-digit numbers qualify (since after placing '1', the next digit must be ≤ '0', but the smallest allowed digit is '1'). Final answer: 20.

This example shows how the tight constraint works without any additional DP state. The first loop handles "shorter numbers" analytically, and the second loop handles "same-length numbers" with the tight constraint propagated digit by digit.

Full Example: Count Numbers with Unique Digits

LeetCode 357. Count Numbers with Unique Digits asks: given n, count all numbers in [0, 10^n) that have all distinct digits.

This is a classic digit DP problem where the state is a bitmask of digits already used, and the started flag handles leading zeros:

from functools import lru_cache

def countNumbersWithUniqueDigits(n):
    if n == 0:
        return 1
    limit = 10 ** n - 1
    digits = [int(d) for d in str(limit)]
    num_len = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos, tight, mask, started):
        if pos == num_len:
            return 1  # every number is valid (we only placed unique digits)
        bound = digits[pos] if tight else 9
        count = 0
        for d in range(0, bound + 1):
            new_tight = tight and d == bound
            if not started and d == 0:
                count += dp(pos + 1, new_tight, mask, False)
            else:
                if mask & (1 << d):
                    continue  # digit already used
                count += dp(pos + 1, new_tight, mask | (1 << d), True)
        return count

    return dp(0, True, 0, False)

The bitmask tracks which of the 10 digits (0-9) have been placed so far. The started flag prevents marking leading zeros as "used." Without it, the number 10 would appear to reuse digit 0 (since the leading zero in "010" would mark 0 as taken). The state space is $O(n \times 2 \times 1024 \times 2) \approx 73{,}000$ states for $n = 8$, each trying at most 10 digits.

Recognizing this pattern

You're probably looking at digit DP when:

• The problem asks you to count integers in $[L, R]$ (or $[1, N]$) satisfying some property, and the bounds are absurd, with $N$ up to $10^9$, $10^{15}$, or $10^{18}$ that rule out enumeration.
• The property is defined at the digit level: digit sum, no two adjacent equal digits, contains/avoids a specific digit, divisibility by $K$, all distinct digits, etc.
• The answer asks "how many" or "the k-th" valid number, not "find one example."
• Phrases like "numbers whose digits...", "no consecutive...", "lucky numbers," or "numbers at most N given digit set" appear in the prompt.
• You catch yourself wanting to write a for loop from 1 to N but $N$ is a 64-bit integer.

Common templates:

• Digit sum / running aggregate: state is the partial sum (or partial value mod K). Example: Numbers With Repeated Digits.
• Bitmask of used digits: state is a 10-bit mask plus a started flag for leading zeros. Example: Count Numbers with Unique Digits.
• Last-digit / adjacency constraint: state is the previous digit placed, enforcing local rules. Example: Count Special Integers.
• Allowed digit set + tight only: no extra state, just the tight flag picking from a restricted alphabet. Example: Numbers At Most N Given Digit Set.
• Range $[L, R]$ via $f(R) - f(L-1)$: wrap any single-bound counter to handle ranges. Example: Non-negative Integers without Consecutive Ones.