Have you ever come across a problem that asks you to count how many numbers in a range [L, R] satisfy a specific property, only to realize that R can be up to 10^15?

Your first instinct might be to write a simple for loop and check each number one by one. But when R is that massive, an O(N) loop will result in a Time Limit Exceeded error.

This is exactly where Digit Dynamic Programming saves the day. Instead of iterating through numbers, we construct them digit by digit, caching the states as we go.

We are going to look at a classic Digit DP problem to understand how to design states, handle boundaries, and deal with the leading zeros edge case.

The Problem Statement

You are given three integers l, r and k.

A number is considered good if the absolute difference between every pair of adjacent digits is at most k. Return the number of good integers in the range [l, r].

Example 1:

1
2
3
4
5
6
7
8
9

Input: l = 10, r = 15, k = 1
Output: 3

Explanation:
The good integers in the range are 10, 11, and 12.
For 10, abs(1 - 0) = 1.
For 11, abs(1 - 1) = 0.
For 12, abs(1 - 2) = 1.
All these differences are at most k = 1. Thus, the answer is 3.

Example 2:

1
2
3
4
5
6
7
8

Input: l = 201, r = 204, k = 2
Output: 2

Explanation:
The good integers in the range are 201 and 202.
For 201, abs(2 - 0) = 2 and abs(0 - 1) = 1.
For 202, abs(2 - 0) = 2 and abs(0 - 2) = 2.
Thus, the answer is 2.

Constraints:

  • 10 <= l <= r <= 10^15
  • 0 <= k <= 9

The Prefix Counting

The standard trick for any range counting problem [L, R] is to realize that: Count in [L, R] = Count in [0, R] - Count in [0, L - 1]

Instead of writing a complex function that stays strictly between L and R, we just write a function solve(num) that counts all valid numbers from 0 to num. Then, we simply calculate the difference.

Designing the State

Digit DP is basically a decision tree where we pick a number from 0 to 9 at each step to build our integer. To memoize this, we need to know our exact context.

We need 4 parameters for our state:

  1. i (index): Which digit are we currently placing (from left to right)?
  2. prev (previous digit): What was the last digit we placed? We need this to check if abs(prev - current) <= k.
  3. tight (is bound restricted?): This is crucial. If we are finding valid numbers up to 345, and our first digit is 3, the next digit cannot go up to 9. It is restricted by the upper bound 4. If tight is true, our upper limit is num[i]. If false, we can safely loop up to 9.
    4.leadZero (leading zeros): Numbers can be shorter than R. For instance, 0042 is just 42. When building 0042, the first non-zero digit is 4. We shouldn’t check the difference between 0 and 4 because those leading zeros don’t actually exist in the number. If leadZero is true, we ignore the k constraint.

The C++ Implementation

Let’s look at the complete code and break down the transitions.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

class Solution {
    using ll = long long;
    using table = vector<vector<vector<vector<ll>>>>;
public:
    ll solve(table &memo, string &num, int i, bool tight, bool leadZero, int prev,
        int k) {
        // We successfully formed a valid number
        if (i == num.size()) return 1;

        // Cached result if we have been in this state
        if (memo[i][tight][leadZero][prev] != -1) {
            return memo[i][tight][leadZero][prev];
        }

        ll total = 0;
        int lb = 0;
        // Upper bound is restricted by the actual number if tight is true
        int ub = tight ? num[i] - '0' : 9; 
        for (int j = lb; j <= ub; j++) {
            // If the number has started, enforce the k difference rule
            if (!leadZero && abs(prev - j) > k) continue;
            
            /* The next state is tight only if the current state is tight 
                and we picked the max possible digit at this level
             */
            bool tightP = (tight && (j == ub));
            /* We are still placing leading zeros if we were previously 
                placing them  and the current digit is also zero
            */
            bool leadZeroP = (leadZero && (j == 0));

            // Count valid numbers for the remaining positions
            total += solve(memo, num, i + 1, tightP, leadZeroP, j, k);
        }

        return memo[i][tight][leadZero][prev] = total;
    }

    ll goodIntegers(ll l, ll r, int k) {
        string num1 = to_string(l - 1);
        string num2 = to_string(r);

        int n = num2.size();
        int m = num1.size();
        
        // Memoization tables: [index][tight][leadZero][prev]
        table memo1(n, vector<vector<vector<ll>>>(
            2, vector<vector<ll>>(2, vector<ll>(10, -1))
        ));
        table memo2(m, vector<vector<vector<ll>>>(
            2, vector<vector<ll>>(2, vector<ll>(10, -1))
        ));

        // Count for [0, R]
        ll upper = solve(memo1, num2, 0, true, true, 0, k);
        // Count for [0, L - 1]
        ll lower = solve(memo2, num1, 0, true, true, 0, k);

        return upper - lower;
    }
};

Understanding the Transitions

The hardest part of Digit DP is getting the tight and leadZero transitions right inside the loop:

  • tightP = (tight && (j == ub)) Imagine our limit is 345. If we pick 2 as our first digit, the prefix is smaller than 3, meaning the rest of the digits can be anything from 00 to 99. The tight constraint turns off! But if we pick 3 (which equals ub), we are still walking on a tightrope, and the next digit is restricted to 4.
  • leadZeroP = (leadZero && (j == 0)) If we are building the number 007, the first two digits are leading zeros. As long as we keep placing 0s, leadZeroP stays true. The moment we place the 7, leadZeroP turns false forever for this recursive branch, and the abs(prev - j) <= k rule activates.

Complexity Analysis

To understand how fast Digit DP is, we just need to calculate two things: the number of unique states, and the work done per state.

1. Number of Unique States: Our memo table has 4 dimensions:

  • i (Index): The number of digits. Since R <= 10^15, the number can have at most 15 digits.
  • tight (Boolean): 2 possible values (true or false).
  • leadZero (Boolean): 2 possible values (true or false).
  • prev (Previous digit): 10 possible values (0 through 9).

Total unique states = 15 x 2 x 2 x 10 = 600 states.

2. Work Done Per State: Inside our solve function, if the state isn’t already cached, we run a for loop that iterates through the possible next digits. This loop runs at most 10 times.

Total Time Complexity: O(States x Transitions) = O(600 x 10) = 6000 operations

So, instead of running a brute-force loop 10^15 times, Digit DP solution finds the exact answer in roughly 6,000 operations executing in a fraction of a millisecond!

Space Complexity: O(log₁₀(R) x 2 x 2 x 10). This is simply the size of our 4D memo array (600 integers), plus the maximum depth of the recursion call stack. It uses virtually zero memory.

Conclusion

Digit DP looks intimidating at first, but once you map out the state parameters (i, tight, leadZero, and whatever specific condition the problem asks for like prev), it becomes a highly repeatable template.

Next time you see a problem asking to count valid numbers up to astronomical bounds, you’ll know exactly which tool to pull out of your algorithm toolkit!