3869. Count Fancy Numbers in a Range

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given two integers l and r.

An integer is called good if its digits form a strictly monotone sequence, meaning the digits are strictly increasing or strictly decreasing. All single-digit integers are considered good.

An integer is called fancy if it is good, or if the sum of its digits is good.

Return an integer representing the number of fancy integers in the range [l, r] (inclusive).

A sequence is said to be strictly increasing if each element is strictly greater than its previous one (if exists).

A sequence is said to be strictly decreasing if each element is strictly less than its previous one (if exists).

Let's break down the key ideas to make sure the requirements are clear:

A number's digits must be checked from left to right. For example, 135 is strictly increasing (1 < 3 < 5), so it is good. Likewise, 951 is strictly decreasing (9 > 5 > 1), so it is good.
Any number with a single digit (such as 0 through 9) is automatically good.
If a number's digits are not strictly monotone (for example 122 or 132), then the number itself is not good. However, you should also look at the sum of its digits. If that sum is itself a good number, then the original number still counts as fancy.
For instance, take a number whose digits add up to 135. The sum 135 has strictly increasing digits, so the number is fancy even though its own digits may not be monotone.

In summary, for each integer x in the range [l, r], you need to count it if either:

The digits of x form a strictly increasing or strictly decreasing sequence, or
The sum of the digits of x forms a strictly increasing or strictly decreasing sequence.

Your task is to return the total count of such fancy integers within [l, r].

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dynamic Programming?

This problem maps to Dynamic Programming through a short path in the full flowchart.

Digit DP over digit positions tracking monotone state and running sum, with range handled by prefix difference.

Open in Flowchart

Intuition

The first thing to notice is the size of the range. The values l and r can be very large, so we cannot simply loop through every integer from l to r and test each one individually. This pushes us toward a counting technique that works on the digit structure of numbers rather than the numbers themselves.

When a problem asks us to count how many numbers in a range satisfy some condition that depends on their digits, the natural tool is Digit DP. Instead of iterating over numbers, we build numbers digit by digit and count how many valid completions exist. To handle the range [l, r], we use the classic trick of computing the answer for [0, r] minus the answer for [0, l-1]. This reduces the problem to counting fancy numbers up to a given upper bound.

Next, let's think about what information we need to track as we place digits one at a time:

We must know whether the digits placed so far are still strictly increasing, strictly decreasing, or have already broken monotonicity. This tells us if the number itself is good. We can capture this with a small state value: state 0 for "at most one digit so far", state 1 for "strictly increasing", state 2 for "strictly decreasing", and state 3 for "no longer monotone".
To compare each new digit with the previous one, we need to remember the previous digit value prev.
The fancy condition also depends on the sum of digits, so we accumulate a running sum s as we go.
As with all digit DP, we carry a lim flag that tells us whether we are still bound by the upper limit's digit at the current position. When lim is true, the current digit can only go up to the bound's digit; otherwise it can range freely from 0 to 9.

Now consider what happens when we finish placing all digits. There are two ways a number qualifies as fancy:

If the monotonicity state is not 3, the digits themselves form a strictly monotone sequence, so the number is good and we count it directly.
If the state is 3, the number itself is not good, but it can still be fancy if the digit sum is good. So we check whether the accumulated sum s is a good number.

The clever part is the check on the digit sum. The maximum possible digit sum is small (a number with many 9s still gives a sum well under a few hundred), so the sum s is at most a three-digit number. This means checking whether s is good is easy:

If s < 100, it has at most two digits. A two-digit number is good unless both digits are equal, and the only way two equal digits sum to a two-digit value is when s is a multiple of 11 (like 11, 22, 33). So we just check s % 11 != 0.
If s >= 100, it is a three-digit number, and we directly verify that its hundreds, tens, and units digits form a strictly monotone sequence. Because the leading digit of a small three-digit sum is 1 or 2, checking strictly increasing (hundreds < tens < units) is sufficient.

Putting these pieces together, the state of our recursion becomes dfs(pos, s, prev, st, lim). By memoizing on the parts of the state that are independent of the limit (position, sum, previous digit, and monotone state), we avoid recomputing the same subproblems and keep the solution efficient. We clear the cache between the two boundary computations because the num string changes, which changes the meaning of the states tied to it.

Pattern Learn more about Math and Dynamic Programming patterns.

Solution Approach

Solution 1: Digit DP

We first define a helper function check(s) to determine whether an integer s is a good number. Because the digit sum is always small, s can have at most three digits, which makes the check simple:

For s < 100, the value has at most two digits. A two-digit number fails to be strictly monotone only when its two digits are equal, and that happens exactly when s is a multiple of 11. So we return s % 11 != 0.
For s >= 100, the value has three digits. We extract the tens digit s // 10 % 10 and the units digit s % 10, and verify that the digits are strictly increasing. Since the hundreds digit of such a small sum is 1 or 2, checking 1 < s // 10 % 10 < s % 10 is enough to confirm strict monotonicity.

Next, we use digit DP to count fancy numbers up to a given bound. We define a recursive function dfs(pos, s, prev, st, lim), where:

Integer pos is the current digit position being processed, from the most significant digit to the least.
Integer s is the running sum of the digits placed so far.
Integer prev is the value of the previous digit.
Integer st is the monotone state of the digit sequence so far: state 0 means at most one digit has been placed, state 1 means strictly increasing, state 2 means strictly decreasing, and state 3 means no longer strictly monotone.
Boolean lim indicates whether the current digit is still constrained by the upper bound.

Base case. When pos reaches len(num), we have completed a number:

If st != 3, the digits form a strictly monotone sequence, so the number is good, and we return 1.
Otherwise the number itself is not good, so we fall back to checking the digit sum, returning int(check(s)).

Transition. For each position, we determine the upper limit of the current digit. If lim is true, the digit can range over [0, num[pos]]; otherwise it ranges over [0, 9]. For each candidate digit i, we compute the next monotone state nxt_st based on the current state st:

If st == 0: when prev == 0 we stay in state 0 (still effectively no meaningful digit yet for leading zeros); if i > prev we move to state 1; if i < prev we move to state 2; if i == prev we move to state 3.
If st == 1: stay in state 1 only if i > prev, otherwise break to state 3.
If st == 2: stay in state 2 only if i < prev, otherwise break to state 3.
If st == 3: it remains 3 once monotonicity is broken.

We then accumulate the result by recursing into dfs(pos + 1, s + i, i, nxt_st, lim and i == up). The new lim stays true only when we are still pinned to the bound and the chosen digit equals the maximum allowed digit.

Memoization. The recursion is decorated with @cache so repeated states are not recomputed. The cached state effectively keys on (pos, s, prev, st, lim), which keeps the number of distinct subproblems small.

Combining the boundaries. We answer the range query by computing the count up to r and subtracting the count up to l - 1:

Set num = str(l - 1) and run dfs(0, 0, 0, 0, True) to get a.
Call dfs.cache_clear() to reset the cache, because the meaning of the states (especially the lim flag) is tied to the current num string.
Set num = str(r) and run dfs(0, 0, 0, 0, True) to get b.
Return b - a.

This approach builds every valid number digit by digit while tracking just enough state to decide both whether the number is good and whether its digit sum is good, giving an efficient count over the entire range without enumerating each integer individually.

Example Walkthrough

Let's trace through a small example to see how the Digit DP counts fancy numbers. Suppose we want to count fancy integers in the range [10, 13], so l = 10 and r = 13.

Step 1: Reduce the range query.

We compute count(0, 13) - count(0, 9). So we run the DP twice:

First with num = "9" (this is l - 1 = 9) to get a.
Then with num = "13" (this is r = 13) to get b.

The answer will be b - a.

Step 2: Compute a = count(0, 9) with num = "9".

Here num has length 1, so we only place a single digit. Starting at dfs(0, 0, 0, 0, True), the digit i can range over [0, 9]. For each choice we recurse to dfs(1, ...), which hits the base case at pos == 1.

For every single digit 0 through 9, the state stays 0 (at most one meaningful digit), so st != 3 at the base case, and each returns 1.
Total: a = 10 (the numbers 0 through 9 are all good).

Step 3: Compute b = count(0, 13) with num = "13".

Now num has length 2. We start at dfs(0, 0, 0, 0, True). The first digit can range over [0, 1] because we're limited by the bound's leading digit 1.

Branch: first digit = 0 (lim becomes False since 0 != 1).

This covers numbers 00–09, i.e. 0–9. The second digit ranges freely over [0, 9].

With prev = 0 and st = 0, placing any digit keeps st = 0 (leading zero handling), so all 10 completions are good → contributes 10.

Branch: first digit = 1 (lim stays True since 1 == 1).

Now prev = 1, st = 0, s = 1. The second digit is limited to [0, 3] (the bound's second digit). We evaluate each candidate:

2nd digit `i`	compare to `prev=1`	`nxt_st`	digit sum `s`	good?	counts
`0`	`0 < 1`	`2` (decreasing)	`1`	state ≠ 3 → good	`1`
`1`	`1 == 1`	`3` (broken)	`2`	check sum `2`: single digit good	`1`
`2`	`2 > 1`	`1` (increasing)	`3`	state ≠ 3 → good	`1`
`3`	`3 > 1`	`1` (increasing)	`4`	state ≠ 3 → good	`1`

This branch contributes 4 (numbers 10, 11, 12, 13).

Notice 11 is interesting: its digits 1, 1 are equal, so the number itself is not good (st = 3). But we fall back to checking the digit sum s = 2, which is a single-digit good number, so 11 still counts as fancy.

So b = 10 + 4 = 14.

Step 4: Combine.

answer = b - a = 14 - 10 = 4

This matches the expected result: in [10, 13], the numbers 10 (decreasing), 11 (sum is 2, good), 12 (increasing), and 13 (increasing) are all fancy, giving a count of 4.

The key takeaways from this trace:

The range is handled by subtracting two prefix counts.
The lim flag tightens the digit choices only along the boundary path (first digit 1, then [0,3]), while off-boundary branches range freely over [0,9].
Even when a number's own digits break monotonicity (like 11), the digit-sum check (check(s)) gives it a second chance to qualify as fancy.

Solution Implementation

1from functools import cache
2
3
4class Solution:
5    def countFancy(self, l: int, r: int) -> int:
6        # Validate a number `digit_sum` against the "fancy" condition.
7        def check(digit_sum: int) -> bool:
8            # For sums below 100, fancy means not divisible by 11.
9            if digit_sum < 100:
10                return digit_sum % 11 != 0
11            # Otherwise, the tens digit must lie strictly between 1 and the units digit.
12            return 1 < digit_sum // 10 % 10 < digit_sum % 10
13
14        @cache
15        def dfs(pos: int, digit_sum: int, prev: int, state: int, is_limit: bool) -> int:
16            # Reached the end of the number: decide whether to count it.
17            if pos >= len(num):
18                # State != 3 means the digits stayed monotonic; always counts.
19                if state != 3:
20                    return 1
21                # Mixed pattern: count only if the digit sum passes the check.
22                return int(check(digit_sum))
23
24            # Upper bound for the current digit (tight bound only when is_limit holds).
25            upper = int(num[pos]) if is_limit else 9
26            res = 0
27            for digit in range(upper + 1):
28                next_state = state
29                if state == 0:
30                    # Initial state: establish the trend on the first meaningful comparison.
31                    if prev == 0:
32                        next_state = 0          # Still leading/equal-to-zero region.
33                    elif digit > prev:
34                        next_state = 1          # Begin increasing.
35                    elif digit < prev:
36                        next_state = 2          # Begin decreasing.
37                    else:
38                        next_state = 3          # Equal digits -> mixed.
39                elif state == 1:
40                    # Increasing so far: must keep strictly increasing.
41                    next_state = 1 if digit > prev else 3
42                elif state == 2:
43                    # Decreasing so far: must keep strictly decreasing.
44                    next_state = 2 if digit < prev else 3
45                else:
46                    # Already mixed: stays mixed.
47                    next_state = 3
48
49                res += dfs(
50                    pos + 1,
51                    digit_sum + digit,
52                    digit,
53                    next_state,
54                    is_limit and digit == upper,
55                )
56            return res
57
58        # Count fancy numbers in [0, l - 1].
59        num = str(l - 1)
60        lower_count = dfs(0, 0, 0, 0, True)
61        dfs.cache_clear()
62
63        # Count fancy numbers in [0, r].
64        num = str(r)
65        upper_count = dfs(0, 0, 0, 0, True)
66
67        # Numbers in [l, r] = count(r) - count(l - 1).
68        return upper_count - lower_count
69

1class Solution {
2    // String representation of the current upper bound being processed
3    private String num;
4    // Memoization table: f[pos][digitSum][prevDigit][state]
5    private Long[][][][] memo;
6
7    /**
8     * Counts fancy numbers in the closed interval [l, r].
9     * Uses the standard digit DP technique: count(r) - count(l - 1).
10     */
11    public long countFancy(long l, long r) {
12        // Count fancy numbers in [0, l - 1]
13        num = String.valueOf(l - 1);
14        init();
15        long lowerCount = dfs(0, 0, 0, 0, true);
16
17        // Count fancy numbers in [0, r]
18        num = String.valueOf(r);
19        init();
20        long upperCount = dfs(0, 0, 0, 0, true);
21
22        // Numbers in [l, r] = count[0, r] - count[0, l - 1]
23        return upperCount - lowerCount;
24    }
25
26    /**
27     * Initializes (resets) the memoization table based on the length of `num`.
28     * Dimensions:
29     *   - position:   n           (0 .. n-1)
30     *   - digit sum:  9 * n + 1   (max possible sum is 9 per digit)
31     *   - prev digit: 10          (0 .. 9)
32     *   - state:      4           (0,1,2,3 as described in dfs)
33     */
34    private void init() {
35        int n = num.length();
36        memo = new Long[n][9 * n + 1][10][4];
37    }
38
39    /**
40     * Validates a number based on its digit sum `s`.
41     * This is only called when the digit sequence is NOT strictly monotonic
42     * (state == 3 at the end).
43     *
44     * Rules:
45     *   - If s < 100: it is valid only if s is not a multiple of 11.
46     *   - Otherwise:  let `mid` be the tens digit and `last` be the units digit
47     *                 of s; it is valid only if 1 < mid < last.
48     */
49    private boolean check(int s) {
50        if (s < 100) {
51            return s % 11 != 0;
52        }
53        int mid = (s / 10) % 10;  // tens digit of the sum
54        int last = s % 10;        // units digit of the sum
55        return mid > 1 && mid < last;
56    }
57
58    /**
59     * Digit DP recursion.
60     *
61     * @param pos     current digit position being filled (left to right)
62     * @param s       accumulated digit sum so far
63     * @param prev    previously placed digit
64     * @param st      monotonicity state:
65     *                  0 -> no trend established yet (still leading zeros or first digit)
66     *                  1 -> strictly increasing so far
67     *                  2 -> strictly decreasing so far
68     *                  3 -> trend broken (not strictly monotonic)
69     * @param lim     whether the current prefix is still bounded by `num`
70     *                (true means we are tight against the upper limit)
71     * @return        the number of valid completions from this state
72     */
73    private long dfs(int pos, int s, int prev, int st, boolean lim) {
74        // Base case: all positions have been filled
75        if (pos >= num.length()) {
76            // If the number is strictly monotonic (state != 3), it is counted as valid
77            if (st != 3) {
78                return 1;
79            }
80            // Otherwise validate it against the digit-sum rules
81            return check(s) ? 1 : 0;
82        }
83
84        // Use memoized result only when not bounded by the upper limit
85        if (!lim && memo[pos][s][prev][st] != null) {
86            return memo[pos][s][prev][st];
87        }
88
89        // Upper bound for the current digit: limited by `num` if still tight
90        int up = lim ? num.charAt(pos) - '0' : 9;
91        long res = 0;
92
93        // Try every possible digit for the current position
94        for (int i = 0; i <= up; i++) {
95            int nxtSt = st;
96
97            if (st == 0) {
98                // No trend yet
99                if (prev == 0) {
100                    // Still in leading-zero phase; keep state at 0
101                    nxtSt = 0;
102                } else if (i > prev) {
103                    nxtSt = 1; // start increasing
104                } else if (i < prev) {
105                    nxtSt = 2; // start decreasing
106                } else {
107                    nxtSt = 3; // equal digits -> not strictly monotonic
108                }
109            } else if (st == 1) {
110                // Currently increasing
111                if (i > prev) {
112                    nxtSt = 1; // keep increasing
113                } else {
114                    nxtSt = 3; // trend broken
115                }
116            } else if (st == 2) {
117                // Currently decreasing
118                if (i < prev) {
119                    nxtSt = 2; // keep decreasing
120                } else {
121                    nxtSt = 3; // trend broken
122                }
123            } else {
124                // Already broken; remains broken
125                nxtSt = 3;
126            }
127
128            // Recurse to the next position, accumulating the sum and updating the tight flag
129            res += dfs(pos + 1, s + i, i, nxtSt, lim && i == up);
130        }
131
132        // Cache the result for the non-tight branch
133        if (!lim) {
134            memo[pos][s][prev][st] = res;
135        }
136
137        return res;
138    }
139}
140

1class Solution {
2public:
3    long long countFancy(long long l, long long r) {
4        // Validity check applied only to numbers that fall into state 3
5        // (i.e. the increasing/decreasing monotonic chain has been broken).
6        auto check = [&](int sum) -> bool {
7            if (sum < 100) {
8                return sum % 11 != 0;
9            }
10            int midDigit = (sum / 10) % 10;  // tens digit of the sum
11            int lastDigit = sum % 10;        // units digit of the sum
12            return midDigit > 1 && midDigit < lastDigit;
13        };
14
15        // numStr holds the current upper-bound string being processed.
16        std::string numStr = std::to_string(l - 1);
17        int len = numStr.size();
18
19        // Memoization table indexed by:
20        //   [position][digit sum][previous digit][monotonic state]
21        // Max digit sum is bounded by 9 * len, hence the +1 dimension size.
22        std::vector memo(
23            len,
24            std::vector(9 * len + 1,
25                        std::vector(10, std::vector<long long>(4, -1))));
26
27        // Digit DP.
28        //   pos  : current digit position
29        //   sum  : accumulated digit sum so far
30        //   prev : previously placed digit
31        //   state: 0 = leading/flat, 1 = increasing, 2 = decreasing, 3 = broken
32        //   limit: whether we are still tight against the upper bound
33        auto dfs = [&](this auto&& dfs, int pos, int sum, int prev, int state,
34                       bool limit) -> long long {
35            // Base case: all digits placed.
36            if (pos >= len) {
37                // Numbers that never reached the "broken" state count directly.
38                if (state != 3) return 1;
39                // Otherwise apply the validity check on the accumulated sum.
40                return check(sum) ? 1LL : 0LL;
41            }
42
43            // Reuse memoized result only when unconstrained by the upper bound.
44            if (!limit && memo[pos][sum][prev][state] != -1) {
45                return memo[pos][sum][prev][state];
46            }
47
48            int up = limit ? numStr[pos] - '0' : 9;
49            long long res = 0;
50
51            for (int d = 0; d <= up; ++d) {
52                int nextState = state;
53
54                if (state == 0) {
55                    // Still in the leading-zero / flat phase.
56                    if (prev == 0)
57                        nextState = 0;       // keep skipping leading zeros / flats
58                    else if (d > prev)
59                        nextState = 1;       // begin increasing
60                    else if (d < prev)
61                        nextState = 2;       // begin decreasing
62                    else
63                        nextState = 3;       // equal -> broken
64                } else if (state == 1) {
65                    // Currently increasing.
66                    if (d > prev)
67                        nextState = 1;       // stay increasing
68                    else
69                        nextState = 3;       // not strictly greater -> broken
70                } else if (state == 2) {
71                    // Currently decreasing.
72                    if (d < prev)
73                        nextState = 2;       // stay decreasing
74                    else
75                        nextState = 3;       // not strictly smaller -> broken
76                } else {
77                    // Already broken; stays broken.
78                    nextState = 3;
79                }
80
81                res += dfs(pos + 1, sum + d, d, nextState, limit && d == up);
82            }
83
84            // Cache only the unconstrained results.
85            if (!limit) {
86                memo[pos][sum][prev][state] = res;
87            }
88
89            return res;
90        };
91
92        // Count of valid numbers in [0, l - 1].
93        long long lower = dfs(0, 0, 0, 0, true);
94
95        // Reset table and bound for the upper end of the range.
96        numStr = std::to_string(r);
97        len = numStr.size();
98        memo.assign(
99            len,
100            std::vector(9 * len + 1,
101                        std::vector(10, std::vector<long long>(4, -1))));
102
103        // Count of valid numbers in [0, r].
104        long long upper = dfs(0, 0, 0, 0, true);
105
106        // Prefix difference gives the count within [l, r].
107        return upper - lower;
108    }
109};
110

1// Number string of the current upper bound being processed
2let numStr: string;
3// Length of numStr
4let len: number;
5// Memoization table: f[position][digitSum][prevDigit][state]
6let memo: number[][][][];
7
8/**
9 * Validates a number that reached the "peak" state (state 3).
10 * - Numbers below 100 are fancy unless divisible by 11.
11 * - Larger numbers require the tens digit to be > 1 and < the units digit.
12 */
13const check = (value: number): boolean => {
14  if (value < 100) {
15    return value % 11 !== 0;
16  }
17  const tens = Math.floor(value / 10) % 10;
18  const units = value % 10;
19  return tens > 1 && tens < units;
20};
21
22/**
23 * Digit DP traversal.
24 * @param pos     current digit position
25 * @param sum     accumulated digit sum so far
26 * @param prev    previous digit chosen
27 * @param state   0: start/flat, 1: increasing, 2: decreasing, 3: peaked (inc then dec)
28 * @param limited whether the current prefix is still bound by numStr's prefix
29 */
30const dfs = (
31  pos: number,
32  sum: number,
33  prev: number,
34  state: number,
35  limited: boolean,
36): number => {
37  // All digits placed: validate the constructed number.
38  if (pos >= len) {
39    // Only numbers that reached the peak state must satisfy check().
40    if (state !== 3) return 1;
41    return check(sum) ? 1 : 0;
42  }
43
44  // Use cached result when not constrained by the upper bound.
45  if (!limited && memo[pos][sum][prev][state] !== -1) {
46    return memo[pos][sum][prev][state];
47  }
48
49  // Maximum digit allowed at this position.
50  const up = limited ? Number(numStr[pos]) : 9;
51  let res = 0;
52
53  for (let i = 0; i <= up; i++) {
54    let nextState = state;
55
56    if (state === 0) {
57      // Start/flat state: decide the initial trend.
58      if (prev === 0) nextState = 0; // still leading zeros / flat
59      else if (i > prev) nextState = 1; // begin increasing
60      else if (i < prev) nextState = 2; // begin decreasing
61      else nextState = 3; // equal digits => peak (flat at top)
62    } else if (state === 1) {
63      // Increasing: stays increasing while strictly larger, else peaks.
64      if (i > prev) nextState = 1;
65      else nextState = 3;
66    } else if (state === 2) {
67      // Decreasing: stays decreasing while strictly smaller, else peaks.
68      if (i < prev) nextState = 2;
69      else nextState = 3;
70    } else {
71      // Already peaked: remains peaked.
72      nextState = 3;
73    }
74
75    res += dfs(pos + 1, sum + i, i, nextState, limited && i === up);
76  }
77
78  // Cache only the unconstrained results.
79  if (!limited) {
80    memo[pos][sum][prev][state] = res;
81  }
82
83  return res;
84};
85
86/**
87 * Counts fancy numbers in [0, x] via digit DP.
88 */
89const calc = (x: number): number => {
90  numStr = x.toString();
91  len = numStr.length;
92
93  // Initialize memo dimensions: len x (max digit sum + 1) x 10 x 4.
94  memo = Array.from({ length: len }, () =>
95    Array.from({ length: 9 * len + 1 }, () =>
96      Array.from({ length: 10 }, () => Array(4).fill(-1)),
97    ),
98  );
99
100  return dfs(0, 0, 0, 0, true);
101};
102
103/**
104 * Counts fancy numbers in the inclusive range [l, r].
105 */
106function countFancy(l: number, r: number): number {
107  // Prefix-sum style: count up to r minus count up to (l - 1).
108  return calc(r) - calc(l - 1);
109}
110

Time and Space Complexity

Time Complexity

The core of the algorithm is the digit DP function dfs, whose complexity is determined by the number of distinct states multiplied by the work done per state.

State Analysis:

The memoized parameters of dfs are (pos, s, prev, st) — note that states with lim = True form a single path and are not effectively cached, so they do not dominate the count.

pos: the current digit position, ranging over O(log r) values (the number of digits, proportional to log r).
s: the running digit sum. Since each digit contributes at most 9 and there are O(log r) digits, s ranges over O(9 × log r) = O(D × log r) values.
prev: the previous digit, taking D = 10 possible values.
st: the monotonicity state, taking a constant number (4) of values, i.e. O(1).

Hence the number of distinct memoized states is:

O(log r) × O(D × log r) × O(D) × O(1) = O(D^2 × log^2 r)

Work per State:

Inside each dfs call, the loop iterates over digit values for i in range(up + 1), performing O(D) iterations of constant work each.

Total:

O(D^2 × log^2 r) × O(D) = O(D^3 × log^2 r)

Since dfs is invoked twice (once with num = str(l - 1), once with num = str(r), separated by a cache_clear()), this only adds a constant factor. The overall time complexity is:

O(D^3 × log^2 r), where D = 10.

Space Complexity

The dominant space cost comes from the memoization cache, which stores one entry per distinct state (pos, s, prev, st):

O(D^2 × log^2 r)

The recursion depth is O(log r) (bounded by the number of digits), which is dominated by the cache size. Therefore the overall space complexity is:

O(D^2 × log^2 r), where D = 10.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Forgetting to clear the memoization cache between the two boundary computations

The most dangerous and subtle bug in this digit-DP solution is reusing the cached results from the l - 1 computation when computing the count for r.

Why it happens:

The dfs function is decorated with @cache, which keys subproblems on (pos, digit_sum, prev, state, is_limit). However, the function also reads the free variable num inside its body (len(num) and int(num[pos])). The variable num is not part of the cache key, yet the results depend on it.

When you compute the count for l - 1, the cache fills with entries that were derived from num = str(l - 1). If you then switch to num = str(r) without clearing the cache, any state with is_limit == False will be served from the stale cache — but the meaning of "how many digit positions remain" (len(num)) and the bound at each position have changed. This produces silently incorrect results.

The fix is exactly what the reference code does:

num = str(l - 1)
lower_count = dfs(0, 0, 0, 0, True)
dfs.cache_clear()          # <-- critical line

num = str(r)
upper_count = dfs(0, 0, 0, 0, True)

A more robust alternative is to make num an explicit parameter or to wrap the DP inside a helper function whose cache is local, guaranteeing isolation:

def count_up_to(bound: int) -> int:
    num = str(bound)

    @cache
    def dfs(pos, digit_sum, prev, state, is_limit):
        ...

    return dfs(0, 0, 0, 0, True)

return count_up_to(r) - count_up_to(l - 1)

Here each call to count_up_to creates a fresh dfs with its own cache, eliminating any chance of cross-contamination.

Pitfall 2: Caching states where `is_limit` is `True`

Including is_limit=True states in the cache is technically harmless only because each is_limit=True path is unique (there is exactly one tight prefix per num), so they are never reused beneficially and never collide within a single num. The real danger arises across different num values (see Pitfall 1). Some implementations explicitly avoid caching when is_limit is True:

if not is_limit:
    # store / retrieve from cache

This both reduces cache size and removes a class of cross-boundary bugs. With @cache you cannot selectively skip caching, so the explicit cache_clear() (or local-cache) approach is mandatory.

Pitfall 3: Mishandling the leading-zero / `prev == 0` logic

The state machine treats state == 0 with prev == 0 as "still in the leading region." A common mistake is to conflate a genuine leading zero with a digit that happens to be 0 in the middle of a number.

Consider the number 10:

Position 0: digit 1, prev was 0, so state stays 0 (correct — single meaningful digit so far).
Position 1: digit 0, now prev == 1, so 0 < 1 triggers state = 2 (strictly decreasing) — correct, since 1 > 0.

The logic works, but the subtlety is that prev == 0 only keeps us in state 0 when no nonzero digit has been seen yet. Once prev becomes nonzero, a subsequent 0 is treated as a real digit. Verify this carefully:

100: 1 → state 0; 0 (0 < 1) → state 2 (decreasing); 0 again (0 < 0 is false) → state 3 (mixed). The number 100 is not good, and its digit sum is 1, which is good, so 100 should be counted. The DP correctly falls into the check(digit_sum) branch.

A buggy variant that keeps state == 0 whenever the current digit is 0 (rather than checking prev) would incorrectly classify numbers like 1001 as monotone.

Pitfall 4: An off-by-one error when `l == 0`

Computing the lower bound as str(l - 1) breaks when l == 0, because l - 1 == -1 and str(-1) is "-1". The dfs would then try int(num[0]) on the '-' character and crash. Guard against this:

lower_count = count_up_to(l - 1) if l > 0 else 0
return count_up_to(r) - lower_count

Since every single-digit number (including 0) is good, 0 is always fancy, so it must be included when l == 0.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers