Understanding Digit DP Technique: DP Approach Explained

1. Introduction and Core Concepts

The digit dp technique is one of the most elegant and powerful patterns within the dynamic programming paradigm, specifically designed to solve counting problems that involve the decimal representation of numbers. At its core, digit DP answers questions of the form: "How many numbers in the range [L, R] satisfy a given property P?" where the property might relate to the sum of digits, divisibility, presence of certain digits, or more complex constraints. Unlike standard DP problems that operate on arrays or strings, digit DP operates directly on the digits of a number, constructing valid numbers digit-by-digit from most significant to least significant.

Why does this technique matter? A naive approach to counting numbers in a large range, such as between 1 and 10^18, would require iterating through every single number and checking the property — an impossible task due to time constraints. Digit DP transforms this exponential brute-force search into a highly efficient polynomial-time solution by leveraging memoization and the principle of overlapping subproblems. It exploits the fact that the decision for the next digit depends only on a small set of states, such as whether the prefix built so far is already smaller than the prefix of the upper bound (the tight constraint), the sum of digits so far, the remainder modulo some number, or whether a specific digit has appeared.

The fundamental insight behind the digit dp technique is to treat a number as a string of digits and to formulate a recursive function that builds the answer incrementally. The function typically takes parameters like position (pos), tight (whether the prefix is equal to the bound's prefix), leadingZero (whether we are still placing leading zeros), and any additional state required by the problem (like sum or mod). By caching the results of these states, we avoid recomputing the same subproblems thousands of times. This makes digit DP an indispensable tool for competitive programming, algorithmic interviews, and any system that needs to perform fast range queries over numeric properties.

When to Recognize a Digit DP Problem

You should consider the digit dp technique whenever you encounter a problem that asks you to count numbers in a range [L, R] or [0, N] that satisfy a digit-based condition. Keywords like "count numbers with digit sum equal to S", "count numbers divisible by K", "count numbers without digit 4", or "count numbers with non-decreasing digits" are strong indicators. The constraint on R is also a clue: if R can be as large as 10^1000 (given as a string) or 10^18, brute force is intentionally made impossible, signaling that a digit-based DP is expected.

Another hallmark is that the property can be checked incrementally as you build the number. For example, the sum of digits can be accumulated one digit at a time, and divisibility can be tracked using modular arithmetic: new_remainder = (old_remainder * 10 + digit) % K. If the property is decomposable in this way, it is amenable to digit DP. Problems that require counting numbers with a specific pattern, such as "no two adjacent digits are the same" or "number contains at least one '7'", also fit perfectly because the state needed to make the next decision is very small and well-defined.

2. How It Works

The mechanism of digit DP revolves around a digit-by-digit construction of numbers, guided by a tight constraint. Imagine you are given an upper bound N = 543. You want to count all numbers from 0 to N. You build numbers from left to right. At the first position (hundreds place), you can place any digit from 0 to 5. If you place a digit less than 5 (say, 0-4), then for the remaining positions you are free to place any digit from 0 to 9, because the number is already guaranteed to be less than N regardless of what follows. If you place exactly 5, then the next digit is constrained: you can only place 0 to 4 in the tens place to stay within the bound. This binary state — whether the prefix is already strictly less than N (tight = 0) or is still exactly equal to N (tight = 1) — is the cornerstone of the technique.

This tight logic is combined with memoization. The recursive function is typically defined as dp(pos, tight, ...other_states). The pos parameter indicates the current index in the digit array of N (0-indexed from the left). The function returns the count of valid numbers that can be formed from pos to the end, given the current states. For each state, we iterate over all possible digits we can place at pos. The upper limit for the loop is determined by tight: if tight is 1, limit = digits[pos]; if tight is 0, limit = 9. For each digit choice d, the next tight state becomes tight_next = tight and (d == limit). We then recursively call the function for pos+1 with updated states.

Two additional states are crucial for correctness: leadingZero and the problem-specific state. The leadingZero flag handles the fact that numbers have variable lengths. For example, when counting numbers from 0 to 543, the number 7 should be considered as 007. Without a leadingZero flag, we would incorrectly count leading zeros as part of the digit sum or other properties. When leadingZero is true and we place a 0, we remain in the leading zero state and typically do not update other states like sum or remainder. Once we place a non-zero digit, leadingZero becomes false and we start tracking the actual properties of the number.

The State Transition Framework

Formally, the transition can be described as: dp(pos, tight, state) = sum over d in [0, limit] of dp(pos+1, tight_next, new_state(d)). The base case occurs when pos == len(digits), meaning we have constructed a complete number. At this point, we return 1 if the accumulated state satisfies the final condition (e.g., sum == target, remainder == 0), and 0 otherwise. To answer a query for range [L, R], we use the standard prefix difference trick: answer = solve(R) - solve(L-1), where solve(N) counts numbers in [0, N] that satisfy the property. This works because counting up to a bound is the natural operation for digit DP.

Memoization is only applied when tight == 0. When tight == 1, the result depends on the specific suffix of N, which varies for each different N, so caching those states is not reusable across different branches that are tight. In practice, we use a memo table dp[pos][tight][state] or use Python's lru_cache decorator to cache only the non-tight states. This optimization is critical for achieving the desired time complexity and is a common point of confusion for beginners.

3. Implementation

Implementing the digit dp technique in Python is most intuitive using recursion with memoization. The recursive approach directly mirrors the theoretical definition and is easier to debug. We will first look at a generic template that can be adapted to almost any digit DP problem. This template handles the conversion of the number N into a list of digits, the recursive function with tight and leading zero handling, and the memoization layer.

from functools import lru_cache

def count_upto(N_str, target_sum):
    # Convert number to list of integer digits
    digits = list(map(int, str(N_str)))
    n = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos, tight, sum_so_far, leading_zero):
        # Base case: processed all digits
        if pos == n:
            # Valid number if sum equals target (handle 0 correctly)
            return 1 if sum_so_far == target_sum else 0
        
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(0, limit + 1):
            next_tight = tight and (d == limit) if tight else False
            # Actually: tight and (d == digits[pos])
            next_tight = (tight and d == digits[pos])
            next_leading = leading_zero and (d == 0)
            
            next_sum = sum_so_far
            if not next_leading:
                next_sum = sum_so_far + d
                # Pruning: if sum already exceeds target, skip
                if next_sum > target_sum:
                    continue
            
            # If still leading zero, sum should remain 0
            if next_leading:
                next_sum = 0

            total += dp(pos + 1, next_tight, next_sum, next_leading)
        return total

    return dp(0, True, 0, True)

# Example: count numbers in [0, 1000] with digit sum == 5
# print(count_upto("1000", 5))

The code above demonstrates a complete solution for counting numbers with a specific digit sum. Note the careful handling of leading_zero. When we are still in leading zeros, we do not add the digit 0 to the sum. Also, the tight transition is correctly computed as tight and (d == digits[pos]). The use of lru_cache automatically memoizes the states. However, note that tight and leading_zero are booleans, and pos and sum_so_far are integers, all of which are hashable and suitable for caching. For performance, we often convert tight and leading_zero to integers 0/1.

A second common implementation pattern is the iterative (bottom-up) DP, which can be more efficient in languages like Python by avoiding recursion overhead, though it is less common for digit DP due to the complex state transitions. More importantly, many problems require an additional state like modulo. The following example shows how to count numbers divisible by K, which is a frequent interview variation.

from functools import lru_cache

def count_divisible(N_str, K):
    digits = list(map(int, str(N_str)))
    n = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos, tight, mod, leading_zero):
        if pos == n:
            # Number is 0: mod is 0, but we must decide if 0 counts
            # Usually 0 is considered divisible
            return 1 if mod == 0 else 0
        
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(0, limit + 1):
            next_tight = tight and (d == digits[pos])
            next_leading = leading_zero and (d == 0)
            
            next_mod = mod
            if not next_leading:
                # Update remainder: (prev * 10 + d) % K
                next_mod = (mod * 10 + d) % K
            else:
                # Stay at 0 while leading zeros
                next_mod = 0

            total += dp(pos + 1, next_tight, next_mod, next_leading)
        return total

    return dp(0, True, 0, True)

# Count numbers <= 1000 divisible by 7
# print(count_divisible("1000", 7))

For problems where N can be extremely large (e.g., 10^100000 given as a string), recursion depth can become an issue. In such cases, an iterative memoization or increasing recursion limit is needed. The following snippet shows a more optimized, tightly-coded template that is often used in competitive programming to handle tight as an integer and to use a manual memo dictionary for non-tight states only, which saves memory.

def digit_dp_optimized(N_str):
    digits = list(map(int, N_str))
    n = len(digits)
    memo = {}

    def dfs(pos, tight, started, mask):
        # mask could represent any state: sum, mod, has_seven, etc.
        # started is equivalent to not leading_zero
        if pos == n:
            return 1 if started else 1 # count 0 as valid depending on problem
        
        # Only memoize when tight == 0 (not tight)
        if not tight and (pos, started, mask) in memo:
            return memo[(pos, started, mask)]
        
        limit = digits[pos] if tight else 9
        res = 0
        for d in range(limit + 1):
            next_tight = tight and (d == digits[pos])
            next_started = started or (d != 0)
            next_mask = mask
            if next_started:
                # Example transition: track if digit 4 or 9 appeared
                if d == 4 or d == 9:
                    next_mask = 1
                # Or update sum: next_mask = mask + d
            else:
                next_mask = mask
            
            res += dfs(pos + 1, next_tight, next_started, next_mask)
        
        if not tight:
            memo[(pos, started, mask)] = res
        return res

    return dfs(0, True, False, 0)

A fourth pattern is useful when you need to count numbers with a property like "digits are strictly increasing" or "no adjacent digits are equal". Here the state needs to remember the previous digit placed.

from functools import lru_cache

def count_non_decreasing(N_str):
    digits = list(map(int, N_str))
    n = len(digits)

    @lru_cache(maxsize=None)
    def dp(pos, tight, prev_digit, started):
        if pos == n:
            return 1 # all constructed numbers are valid
        
        limit = digits[pos] if tight else 9
        total = 0
        for d in range(0, limit + 1):
            next_tight = tight and (d == digits[pos])
            next_started = started or (d != 0)
            
            # If not started, no constraint on prev_digit
            if not next_started:
                total += dp(pos + 1, next_tight, 0, False)
            else:
                # Enforce non-decreasing: current digit >= prev digit
                # For first real digit, prev_digit is irrelevant
                if not started:
                    # First non-zero digit, any d is allowed
                    total += dp(pos + 1, next_tight, d, True)
                else:
                    if d >= prev_digit:
                        total += dp(pos + 1, next_tight, d, True)
                    # else: skip this d, violates condition
        return total

    # Subtract 1 if you don't want to count 0
    return dp(0, True, 0, False) - 1

# print(count_non_decreasing("100"))

4. Step-by-Step Example

Let us walk through a concrete example to solidify the understanding of the digit dp technique. Problem: Count numbers in the range [0, 20] whose sum of digits equals 2. The valid numbers are 2, 11, and 20, so the answer should be 3. We will trace how solve("20") works. First, N = 20, so digits = [2, 0]. Our DP state is dp(pos, tight, sum_so_far, leading_zero).

We start at dp(0, True, 0, True). pos=0, limit = digits[0] = 2. We will try d = 0, 1, 2.

Branch d=0: next_tight = True and (0 == 2) = False. next_leading = True and (0==0) = True. next_sum = 0. We call dp(1, False, 0, True). Now at pos=1, tight=False, so limit=9. We try d=0..9. For each d, next_leading = True and (d==0). If d=0, next_leading remains True, sum stays 0, we reach pos=2 base case and return 1 if sum==2? No, sum=0 !=2, so returns 0. If d=2, next_leading=False, sum=2, base case returns 1. So this branch will eventually count the number 2 (represented as 02). Similarly, other digits like d=1 will give sum=1 and fail.

Branch d=1: next_tight = True and (1==2)=False. next_leading=False (since d !=0). next_sum=1. Call dp(1, False, 1, False). At pos=1, limit=9. We iterate d=0..9. For d=0, next_sum=1+0=1 !=2, fails. For d=1, next_sum=1+1=2, succeeds and counts number 11. For d=9, sum=10 >2, we prune. So this branch contributes 1.

Branch d=2: next_tight = True and (2==2)=True. next_leading=False. next_sum=2. Call dp(1, True, 2, False). Now pos=1, tight=True, limit=digits[1]=0. So we can only try d=0. next_tight=True and (0==0)=True. next_sum=2+0=2. At pos=2 base case, sum==2 returns 1. This counts number 20. Total = 1 (from 02) + 1 (from 11) + 1 (from 20) = 3.

Visualization of the Recursion Tree

The recursion tree can be visualized as a decision tree where each level corresponds to a digit position. The tight path (following the digits of N exactly) is a single spine from root to leaf (2 -> 0). All branches that diverge from this spine (by choosing a digit smaller than the limit) become free subtrees where tight=False and memoization becomes highly effective. For N=20, the node dp(1, False, 0, True) and dp(1, False, 1, False) are roots of free subtrees that can be reused if they appear elsewhere.

Memoization prevents re-computation. For larger N, like N=54321, the free subtree dp(pos=2, tight=False, sum=5, leading=False) will be encountered via many different paths (e.g., 1 0 X, 0 5 X, etc.), but its result is computed only once. This sharing is what gives digit DP its exponential speedup over brute force. Without memoization, the number of recursive calls would be 10^n, but with memoization it becomes n * state_size * 10.

Finally, to answer the range query [L, R], we compute solve(R) - solve(L-1). For [10, 20] with sum=2, we compute solve(20)=3 and solve(9). For solve(9), digits=[9], valid numbers are 2 and 11? No, 11 >9, so only 2. So solve(9)=1. Answer = 3-1=2 (numbers 11 and 20). Handling L=0 requires care: solve(-1) is not defined, so we handle L==0 as a special case and return solve(R) directly.

5. Complexity Analysis

The efficiency of the digit dp technique is what makes it so valuable for large constraints. Its complexity is determined by the number of states multiplied by the transition cost per state. Let n be the number of digits in N (n = log10(N) + 1), and let S be the size of the additional state space (e.g., sum range, modulo K, etc.). The number of DP states is O(n * 2 * 2 * S), where the two factors of 2 correspond to tight (0/1) and leadingZero (0/1). In practice, we only memoize states where tight=0, so the effective number of cached states is O(n * S).

For each state, we iterate over at most 10 digit choices (0 to limit). Therefore, the time complexity is O(n * S * 10). This is dramatically better than the brute force O(R-L) which is exponential in n. For example, if N = 10^18, n=19, and we are tracking digit sum up to 9*19=171, then S=172. The DP will perform roughly 19 * 172 * 10 ≈ 32,680 operations, whereas brute force would need to check 10^18 numbers. The space complexity is O(n * S) for the memoization table plus O(n) recursion stack depth.

It is important to analyze how S grows with different problem types. If we track remainder modulo K, then S = K, so time is O(n * K * 10). If K is large (e.g., K=10^5), this can become heavy but is still feasible for n=19. If we track both sum and remainder, S becomes product of both, e.g., O(n * sum * K). Optimizations like pruning (skipping branches where sum already exceeds target) can significantly reduce the average-case runtime, though worst-case remains the same.

The table illustrates that digit DP's complexity is pseudo-polynomial in the number of digits, not in the value of N itself. This is the key to its scalability. The best case occurs when pruning is highly effective or when many states are unreachable. For instance, if target sum is very small, many branches where sum exceeds target are pruned early, reducing the effective branching factor. The worst case assumes no pruning and full exploration of all states.

Space complexity is often the limiting factor for more complex states. A DP table of size n=1000 (when N is given as a 1000-digit string) and K=100 would require 100,000 entries, which is manageable. However, if we need to track sum up to 9000, the table becomes 9 million entries, which may require optimization using iterative DP with rolling arrays or using dictionaries for sparse states. In Python, using lru_cache with a large state space can also cause high memory overhead due to Python object overhead, so for very large constraints, an array-based DP with NumPy or PyPy optimizations might be preferred.

6. Variations and Optimizations

While the basic digit dp technique is powerful, several variations and optimizations extend its applicability and improve performance. One common variation is the "digit DP with automaton" where the property to check is described by a finite automaton, such as checking if a number contains a forbidden substring (e.g., "13") or matches a regular expression over digits. In this case, the state includes the current node in the automaton (e.g., using KMP failure function). The transition updates the automaton state based on the next digit, similar to string matching DP.

Another important variation is handling multiple queries efficiently. If you need to answer many queries [L_i, R_i] for the same property, you can precompute the DP table for the maximum R once and reuse it, or use a technique called "digit DP with prefix caching" where you memoize results for all tight=False states globally. Since those states do not depend on N, they can be computed once and shared across all queries. This reduces the per-query cost to just traversing the tight path, which is O(n * 10).

Optimization techniques include state compression and pruning. State compression involves reducing the state dimension. For example, when counting numbers with even digit sum, you only need to track sum parity (0/1) instead of the full sum (0..9n). When counting numbers divisible by 2^k, you only need to track the last k digits, not the entire remainder. Pruning involves early termination: if sum_so_far > target, or if even with the maximum possible remaining sum you cannot reach the target, you can return 0 immediately without exploring further.

Iterative vs. Recursive and Bottom-Up Tricks

Although recursion with memoization is the most common implementation, an iterative bottom-up DP can sometimes be faster and avoid recursion limits. The iterative approach processes digits from left to right, maintaining a DP table dp[tight][state]. At each position, it creates a new table next_dp. This is essentially a BFS over the digit positions and is very cache-friendly. It also makes it easy to implement space optimization by keeping only two layers (current and next).

Another advanced optimization is "meet-in-the-middle digit DP" for extremely large digit lengths (n > 1000) where O(n * S) is still too large. By splitting the number into two halves, you can compute DP for each half separately and combine results using convolution-like techniques. This is rarely needed in interviews but is useful in specialized competitive programming problems. Additionally, for problems where N is up to 10^10^5, you cannot even store digits as integers; you must process N as a string and use digit DP that works directly on the string representation without converting to int.

7. Real-World Applications

Beyond competitive programming and interviews, the digit dp technique has surprising real-world applications in systems that deal with large numeric ranges and digit-based constraints. While you might not see a function explicitly named digit_dp in a web server codebase, the underlying principle of counting numbers with digit properties efficiently is used in various domains.

In databases and data generation, digit DP is used for cardinality estimation and synthetic data generation. For example, when generating test data that must satisfy constraints like "phone numbers must not contain certain digit patterns" or "IDs must have a valid checksum (like Luhn algorithm for credit cards)", digit DP can count how many valid IDs exist in a range and can be adapted to generate the k-th valid ID efficiently. This is crucial for testing database sharding and indexing strategies where you need uniformly distributed but constrained keys.

In networking and security, digit DP-like counting is used in brute-force attack analysis and password strength estimation. Estimating how many passwords of length n satisfy a policy (e.g., at least one digit, no repeated digits) is mathematically similar to digit DP. Network systems that allocate IP addresses or handle numeric routing tables sometimes need to count how many addresses in a CIDR block avoid certain digit patterns for filtering purposes. The tight constraint concept directly maps to prefix matching in IP routing (longest prefix match).

In web servers and rate limiting, consider a system that needs to count requests with IDs in a range that are "lucky" or have special properties for A/B testing or sampling. Instead of scanning a database, a digit DP counter can estimate the count instantly. Furthermore, in cryptography and hashing, analyzing the distribution of hash values that have certain digit properties (like leading zeros in proof-of-work systems such as Bitcoin mining, where you count hashes less than a target) uses similar digit-by-digit comparison logic. The tight comparison is exactly how you check if a hash (interpreted as a large number) is less than the target difficulty.

Another practical use is in digital display and UI testing. When testing systems that render numbers (e.g., odometers, digital clocks), you often need to count how many displayed numbers contain a specific segment pattern (like counting numbers that would require a certain number of LED segments). Digit DP can compute this count for displays with many digits without simulating every number. Similarly, in financial systems, auditing for "round numbers" or numbers with specific divisibility (e.g., amounts divisible by 100) over huge transaction ID ranges can be done efficiently with digit DP.

8. Comparison with Alternatives

To appreciate when to use the digit dp technique, it is helpful to compare it with alternative approaches for solving range counting problems. The most straightforward alternative is brute force enumeration, where you iterate through every number in [L, R] and test the property. While simple to implement and easy to understand, brute force is only feasible for very small ranges (R-L < 10^7). It has no memory overhead but fails catastrophically for large N, as its time complexity is linear in the range size, which is exponential in the number of digits.

Another alternative is using closed-form mathematical formulas, when they exist. For example, counting numbers divisible by K in [0, N] can be done with floor(N/K)+1 in O(1) time. Counting numbers with a specific digit sum can sometimes be done using combinatorics (stars and bars) with inclusion-exclusion to handle the tight constraint and digit limits (0-9). These combinatorial methods are extremely fast (O(n)) when applicable, but they are often complex to derive, error-prone to implement with inclusion-exclusion, and only work for simple properties like sum or count of a digit. They do not generalize easily to properties like "digits are non-decreasing" or automaton-based constraints.

A third alternative is using generating functions or polynomial multiplication. For digit sum problems, the generating function (1 + x + x^2 + ... + x^9)^n can be used to count numbers with sum S, but handling the tight constraint (numbers <= N) still requires digit DP-like logic or inclusion-exclusion over the digits of N. Precomputation with prefix sums is another technique: precompute answers for all N up to a limit (e.g., 10^6) and answer queries in O(1). This works for small limits but is impossible for N up to 10^18.

The comparison makes it clear that digit DP occupies a sweet spot: it is general enough to handle almost any digit-based property, efficient enough to handle astronomically large ranges, and relatively straightforward to implement once the template is understood. While a combinatorial formula might be faster for a very specific problem, the development time and risk of bugs often make digit DP the preferred choice in time-constrained environments like interviews and contests. Brute force should only be used for verification on small test cases or when constraints are guaranteed to be tiny.

9. Common Mistakes and Best Practices

Even experienced programmers make subtle mistakes when implementing the digit dp technique. One of the most frequent errors is mishandling the leading zero state. Forgetting to distinguish between a number that hasn't started (all leading zeros) and the number zero itself can lead to off-by-one errors or incorrect counting of numbers with fewer digits. For example, if you are counting numbers with digit sum 5, the number 5 (represented as 0005) should have sum 5, but if you incorrectly add leading zeros to the sum, you might count 0005 as sum 5 correctly but also miscount 0 as sum 0 when it should be considered. The best practice is to have a clear started or !leadingZero flag and only update problem-specific states when started is true.

Another common pitfall is incorrect memoization of the tight state. Beginners often memoize states where tight=1, which leads to wrong answers because the result for a tight state depends on the suffix of N, which is not the same across different calls. The correct approach is to only memoize when tight==0, or to include the entire suffix of N in the cache key (which defeats the purpose). Using Python's lru_cache without considering this can silently cache tight states and produce incorrect results for subsequent queries with different N. The fix is to either use a manual memo dictionary that checks if not tight before caching, or to use lru_cache but ensure that tight is part of the key and understand that it will still be correct but less efficient (since tight=1 states will be cached but rarely reused).

Off-by-one errors in range queries are also prevalent. The standard trick answer = solve(R) - solve(L-1) requires careful handling when L=0, because L-1 = -1 is not a valid input. You must handle L==0 as a special case. Additionally, when N is given as a string that may be very large, computing L-1 as a string requires implementing string subtraction with borrow, not just int(L)-1 which may overflow. Another mistake is forgetting to convert N to a string or digit list correctly, especially when N is 0.

Best Practices for Robust Implementation

To avoid these pitfalls, follow these best practices: First, always use a well-tested template. Write a generic solve(N_str) function that takes N as a string, converts it to digits, and defines the recursive dp inside. Test this template on small brute-force cases (e.g., N=100) to verify correctness before scaling to large N. Second, clearly define your DP state and base case. Write down what each parameter means and what the return value represents (e.g., "returns count of valid numbers from pos to end given tight, sum, and started"). This documentation prevents logic errors.

Third, use pruning and early returns to improve performance and avoid unnecessary recursion. If sum_so_far > target, return 0 immediately. If you can compute the maximum possible remaining sum (9 * remaining_positions) and sum_so_far + max_remaining < target, also return 0. Fourth, handle data types carefully: use Python's big integers or strings for large N, and be mindful of recursion depth. For n > 1000, increase recursion limit with sys.setrecursionlimit(10000) or switch to iterative DP. Finally, always test edge cases: N=0, N=10^k, L=R, and properties that include or exclude 0.

• Always separate leading zero logic from tight logic; do not merge them into a single flag.
• Only memoize non-tight states for correctness and efficiency.
• Validate with brute force for small N (e.g., N <= 1000) using a simple loop.
• Use string manipulation for L-1 when L is large to avoid overflow.
• Document state meaning and ensure base case correctly handles the number 0.

10. Interview Questions

Digit DP is a favorite topic for senior-level algorithmic interviews because it tests understanding of DP, recursion, memoization, and careful state management. Interviewers often start with a simple variant and then add twists. Here are common questions you should be prepared to answer, along with the expected approach.

Question 1: Count numbers with digit sum equal to S in range [L, R] where R can be up to 10^1000. This is the classic digit DP problem. The expected answer is to implement solve(N) that counts numbers in [0, N] with sum S using DP with states pos, tight, sum, leadingZero. The complexity should be O(n * S * 10). The interviewer will check if you handle leading zeros correctly and if you use the prefix difference trick. A follow-up might be to handle S up to 9*1000 = 9000, which requires optimizing space or using pruning.

Question 2: Count numbers in [0, N] that do not contain the digit 4 and are not divisible by 4 (or similar "unlucky" numbers). This tests combining multiple states. You need to track two properties: hasFour (boolean) and mod4 (remainder). The DP state becomes dp(pos, tight, hasFour, mod, leadingZero). The base case returns 1 if hasFour==False and mod !=0 (or mod==0 depending on definition). The interviewer wants to see if you can correctly update both states simultaneously and handle leading zeros so that the number 0 is not incorrectly flagged as containing 4.

Question 3: Given N, count numbers <= N where digits are strictly increasing (e.g., 123, 129, but not 122). This tests the "previous digit" state. The DP needs to remember prev_digit to enforce the increasing constraint. State: dp(pos, tight, prev_digit, started). Transition: if not started and d==0, stay not started; else if not started, any d is allowed; else require d > prev_digit. The base case always returns 1. This question checks if you can handle state that depends on the previous choice, not just an accumulated sum.

Question 4: How would you find the K-th smallest number in [0, N] that satisfies a property P, without enumerating all numbers? This is an advanced extension that tests if you understand how to use digit DP for order statistics. The technique is to use digit DP counting as a subroutine for digit-by-digit construction: to find the K-th number, you build it from most significant digit to least, at each position trying digits from 0 to 9 and using digit DP to count how many valid numbers exist with that prefix. If count >= K, you choose that digit; otherwise, you subtract count from K and try the next digit. This is similar to finding K-th lexicographical string and demonstrates deep understanding.

Question 5: What is the time and space complexity of your digit DP solution, and how would you optimize it if K (mod value) is large, say K=10^5? This tests complexity analysis and optimization knowledge. You should answer O(n*K*10) time and O(n*K) space, and propose optimizations like using iterative DP with only two rows to reduce space to O(K), using pruning, or using meet-in-the-middle if n is also large. You might also mention that if K is large but n is small (19 digits), O(n*K) is still feasible (1.9 million states), but if both are large, you need more advanced techniques like using BFS with dictionary for sparse states.

• Practice implementing the template from scratch without looking, as interviewers often ask for whiteboard coding.
• Be ready to explain the tight and leadingZero flags verbally and why they are necessary.
• Prepare to discuss trade-offs between recursive memoization and iterative DP.
• Have a brute-force verifier ready to test your solution on small inputs during the interview.