2801. Count Stepping Numbers in Range

Problem Description

The task is to find the count of stepping numbers between two given numbers. A stepping number is defined as an integer where each pair of adjacent digits differs by exactly 1. For instance, 123 and 434 are stepping numbers, whereas 145 and 650 are not. The given boundaries for the search are low and high, which are provided as strings. We need to count how many stepping numbers are there in the range from low to high, inclusive. It's important to note that stepping numbers should not start with zero when considering the range. Since the total count could be very large, we have to return the result modulo 10^9 + 7.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

The intuition behind the solution is to use depth-first search (DFS) to construct stepping numbers and count them. Since we have to deal with potential large integers provided as strings, we can't simply iterate through all numbers between low and high. Instead, we approach this by constructing the stepping numbers digit by digit from left to right, making sure that each digit we add differs by 1 from the previous digit.

We use a DFS algorithm with dynamic programming (DP) to avoid recomputing the same subproblems. Here's the process:

Starting from the leftmost digit, we can pick the next digit such that the absolute difference between it and the previous digit is exactly 1.
We make use of several conditions:
- lead: A flag to check if we're still in the leading zero part of a number.
- limit: A flag to indicate if we have to limit the current digit to be less than or equal to the corresponding digit in high; if not, we can go up to 9.
- pre: The previous digit in the number we are constructing. This is -1 at the start because we have no previous digit initially.
The DFS continues until we've tried all possibilities for constructing stepping numbers within the limit. To optimize the process, we cache results of subproblems using Python's @cache decorator.
We count the stepping numbers up to high and subtract the count of stepping numbers just below low to find the number within the range [low, high].

This approach avoids checking every number in the range for being a stepping number and thus is efficient for ranges with large numbers.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution relies on a recursive Depth-First Search (DFS) approach to construct possible stepping numbers and count them.

Here's a step-by-step explanation of the implementation:

Dynamic Programming with Caching: The use of the @cache decorator in Python caches the results of expensive function calls and returns the cached result when the same inputs occur again, thus optimizing the recursive DFS calls.
The DFS Function: The recursive function dfs takes four parameters:
- pos: the current position in the number being constructed.
- pre: the previous digit used in the stepping number.
- lead: a boolean indicator for whether the current digit is leading (to prevent leading zeros).
- limit: a boolean flag that tells us if the current digit has to be lower or equal to the corresponding digit in the target number (high or adjusted low) or if it can go up to 9.
Base Condition: If pos is greater than or equal to the length of the string representing the number (num), it implies we have reached a valid stepping number, and we return 1 if it's not a leading zero (not lead). Otherwise, we continue constructing the number.
Constructing Numbers: We loop over all possible next digits (from 0 to 9 or up to the corresponding digit in num if limit is True). If we are in the leading zero part (lead is True), we only proceed with zero as the next digit. For the other digits, we check if the absolute difference between the current digit (i) and pre is 1, or if we are at the starting position indicated by pre being -1.
Recursive Calls and Modulo Operation: For valid next digits, we make the recursive call to continue to the next position (pos + 1), updating the previous digit to the current digit, and checking the leading and limit flags as applicable. We take the results modulo mod which is 10**9 + 7.
Counting Stepping Numbers: To get the count of stepping numbers in the range [low, high], we first calculate the count of stepping numbers up to high, and then subtract the count of stepping numbers just below low, adjusting low to low - 1 accordingly.
Caching and Clearing Cache: Before calculating the count for the adjusted low, we clear the cache to remove any previously stored results as the num changes.
Final Calculation: We ensure that the final result is within the bounds of the modulo operation before returning it.

Through the DFS approach, we effectively bypass the need to check each number in the range individually, allowing us to handle the problem of large ranges and large numbers represented as strings efficiently.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's take a small example to illustrate the solution approach, walking through an instance of finding stepping numbers between 10 and 21.

Starting Point: We call our DFS function with pos as 0 (pointing to the first digit), pre as -1 (no previous digit), lead as True (we are in the leading part of the number), and limit as True (we require the digits to be less than or equal to those in high, which is 21).
Constructing First Digit: We first try to select the first digit of the number. The first digit of 10 is 1. As we're in the leading part, we can also start with 0 (but it's not valid here as we consider numbers starting with 0), and go up to 2, the first digit of 21.
Moving to the Next Digits: Let’s select 1 as the first digit. For the second digit, the choices are 0 and 2 because they have a difference of 1 from 1. We move forward by making a recursive call to dfs with:
- pos as 1 (moving to the next digit)
- pre as 1 (the previously selected digit)
- lead as False (as now we have a leading digit)
- limit as True or False depending on whether the first digit matches the limit imposed by the corresponding digit in high.
Completing the Number: If we select 2 as the second digit after 1, our number now is 12 which lies in the range [10, 21].
Recursive Calls and Counting: For each recursive call, we check whether we have formed a valid stepping number and increment our count for such numbers. Additionally, since we are constructing numbers one digit at a time, some recursive paths won't result in stepping numbers and will thus not contribute to the count.
Repeating Process: Repeat the process described in steps 1-5 after decrementing low by 1 from 10 to 9, to account for numbers strictly greater than low and less than or equal to high. We also clear the cache before doing this to reset results for the different num.
Calculating Range: Finally, we subtract the count obtained for low - 1 from the count obtained for high to get our answer, which in this case is the count of stepping numbers between 10 and 21. Counting manually, these numbers are 10, 12, and 21, yielding a total count of 3 stepping numbers.

The use of DFS with caching ensures that we don't repeat calculations for similar branches in our search space, making our algorithm efficient for even large inputs.

Solution Implementation

1from functools import lru_cache  # Import lru_cache decorator from functools
2
3class Solution:
4    def count_stepping_numbers(self, low: str, high: str) -> int:
5        # Define the modulo constant for large number handling
6        MOD = 10**9 + 7
7
8        # Define a depth-first search function with memoization using lru_cache
9        @lru_cache(maxsize=None)
10        def dfs(position: int, previous_digit: int, is_leading_zero: bool, is_within_limit: bool) -> int:
11            # Base case: if position equals the length of the number, return 1 (valid stepping number) if not leading zero.
12            if position == len(number):
13                return int(not is_leading_zero)
14
15            # Determine the upper bound of the digit at the current position
16            upper_bound = int(number[position]) if is_within_limit else 9
17            result = 0
18            for digit in range(upper_bound + 1):
19                # If the digit is 0 and it's a leading zero, we continue with the leading zero
20                if digit == 0 and is_leading_zero:
21                    result += dfs(position + 1, previous_digit, True, is_within_limit and digit == upper_bound)
22                # If no previous digit or the absolute difference between the current and previous digit is 1
23                elif previous_digit == -1 or abs(digit - previous_digit) == 1:
24                    result += dfs(position + 1, digit, False, is_within_limit and digit == upper_bound)
25          
26            # Return the result modulo MOD
27            return result % MOD
28
29        # Set the higher limit number for DFS search
30        number = high
31        count_high = dfs(0, -1, True, True)
32
33        # Clear the cache before the second DFS search
34        dfs.cache_clear()
35
36        # Set the lower limit (subtract 1 to include the lower boundary if it's a stepping number itself)
37        number = str(int(low) - 1)
38        count_low = dfs(0, -1, True, True)
39
40        # Return number of stepping numbers in the range, adjusted with modulo
41        return (count_high - count_low) % MOD
42
43# Example usage:
44# sol = Solution()
45# result = sol.count_stepping_numbers("0", "21")
46# print(result)  # Prints the count of stepping numbers between 0 and 21
47

1import java.math.BigInteger;
2
3class Solution {
4    private final int MOD = (int) 1e9 + 7; // Define the modulo constant.
5    private String targetNumber;
6    private Integer[][] memoizationCache;
7
8    // Counts all stepping numbers between 'low' and 'high'.
9    public int countSteppingNumbers(String low, String high) {
10        // Initialize the cache for memoization.
11        memoizationCache = new Integer[high.length() + 1][10];
12        // Set the targetNumber to 'high' to find the upper bound of stepping numbers.
13        targetNumber = high;
14        int countUpToHigh = countWithDfs(0, -1, true, true);
15      
16        // Reset the cache for memoization.
17        memoizationCache = new Integer[high.length() + 1][10];
18        // Calculate the lower bound (one less than 'low') and find count.
19        String adjustedLow = new BigInteger(low).subtract(BigInteger.ONE).toString();
20        targetNumber = adjustedLow;
21        int countBelowLow = countWithDfs(0, -1, true, true);
22      
23        // Return the count within the range making sure to handle negative values.
24        return (countUpToHigh - countBelowLow + MOD) % MOD;
25    }
26
27    // Helper function to recursively find stepping numbers using Depth-First Search (DFS).
28    private int countWithDfs(int position, int previousDigit, boolean isLeadingZero, boolean isWithinLimit) {
29        // Base case: If all digits have been processed, return 1 if it's not a leading zero.
30        if (position >= targetNumber.length()) {
31            return isLeadingZero ? 0 : 1;
32        }
33        // Use memoization to avoid redundant calculations.
34        if (!isLeadingZero && !isWithinLimit && memoizationCache[position][previousDigit] != null) {
35            return memoizationCache[position][previousDigit];
36        }
37      
38        int count = 0;
39        // Define the upper bound for the current digit.
40        int upperLimit = isWithinLimit ? targetNumber.charAt(position) - '0' : 9;
41        // Loop through all possible next digits.
42        for (int currentDigit = 0; currentDigit <= upperLimit; ++currentDigit) {
43            // Skip the iteration if it's a leading zero.
44            if (currentDigit == 0 && isLeadingZero) {
45                count += countWithDfs(position + 1, previousDigit, true, isWithinLimit && currentDigit == upperLimit);
46            } else if (previousDigit == -1 || Math.abs(previousDigit - currentDigit) == 1) {
47                // If the current digit is one step away from previousDigit, continue the DFS.
48                count += countWithDfs(position + 1, currentDigit, false, isWithinLimit && currentDigit == upperLimit);
49            }
50            // Ensure the count is within the allowed modulo range.
51            count %= MOD;
52        }
53      
54        // Store result in memoization cache to reuse later.
55        if (!isLeadingZero && !isWithinLimit) {
56            memoizationCache[position][previousDigit] = count;
57        }
58      
59        return count;
60    }
61}
62

1#include <cstring>
2#include <string>
3#include <functional>
4#include <cmath>
5
6class Solution {
7public:
8    int countSteppingNumbers(std::string low, std::string high) {
9        // Modulo constant for the computations
10        const int MOD = 1e9 + 7;
11
12        // Maximum length of the number
13        int maxLength = high.size();
14      
15        // Cache for saving computation results
16        int cache[maxLength + 1][10];
17
18        // Initialize cache to -1
19        memset(cache, -1, sizeof(cache));
20
21        // The current number we will compute stepping numbers for
22        std::string num = high;
23
24        // The dynamic programming (DFS) function
25        std::function<int(int, int, bool, bool)> dfs = [&](int position, int previousDigit, bool isLeading, bool isLimited) {
26            // If we are at the end of the number
27            if (position >= num.size()) {
28                // If we are still leading (no digits yet), exclude this case
29                // If not leading, count this as 1 valid stepping number
30                return isLeading ? 0 : 1;
31            }
32            // Use cached result if possible
33            if (!isLeading && !isLimited && cache[position][previousDigit] != -1) {
34                return cache[position][previousDigit];
35            }
36            // Calculate the max digit we can use next
37            int upperBound = isLimited ? num[position] - '0' : 9;
38            int ans = 0; // Accumulates the number of valid stepping numbers
39          
40            // Try all possible digits
41            for (int currentDigit = 0; currentDigit <= upperBound; ++currentDigit) {
42                if (currentDigit == 0 && isLeading) {
43                    // Skip the leading zeros
44                    ans += dfs(position + 1, previousDigit, true, isLimited && currentDigit == upperBound);
45                } else if (previousDigit == -1 || std::abs(previousDigit - currentDigit) == 1) {
46                    // If no digit set yet or the current digit is a step away from the previous one
47                    ans += dfs(position + 1, currentDigit, false, isLimited && currentDigit == upperBound);
48                }
49                ans %= MOD; // Keep ans within bounds of MOD
50            }
51          
52            // Cache the result if not leading or limited
53            if (!isLeading && !isLimited) {
54                cache[position][previousDigit] = ans;
55            }
56            return ans;
57        };
58
59        // Calculate the counts for the 'high' number
60        int countHigh = dfs(0, -1, true, true);
61
62        // Clear the cache for next computation
63        memset(cache, -1, sizeof(cache));
64      
65        // Adjust 'low' to include its boundary in the count
66        for (int i = low.size() - 1; i >= 0; --i) {
67            if (low[i] == '0') {
68                low[i] = '9';
69            } else {
70                low[i] -= 1;
71                break;
72            }
73        }
74        num = low;
75      
76        // Calculate the counts for the 'low' number
77        int countLow = dfs(0, -1, true, true);
78      
79        // Return the difference, adjusted by MOD to keep it positive
80        return (countHigh - countLow + MOD) % MOD;
81    }
82};
83

1// Constants for modulus to avoid large numbers.
2const MODULUS = 1e9 + 7;
3
4// This function counts all stepping numbers within the given range [low, high].
5function countSteppingNumbers(low: string, high: string): number {
6    // Get the length of the 'high' string, representing the upper limit.
7    const maxDigits = high.length;
8
9    // Initialize a memoization array to store results of subproblems.
10    let memo: number[][] = Array(maxDigits + 1)
11        .fill(0)
12        .map(() => Array(10).fill(-1));
13
14    // This function implements a depth-first search algorithm to find all valid stepping numbers.
15    const dfs = (position: number, previousDigit: number, isLeadingZero: boolean, isLimit: boolean): number => {
16        // Base case when we have reached the end of the number.
17        if (position >= num.length) {
18            return isLeadingZero ? 0 : 1;
19        }
20
21        // Use memoized values if available for non-leading zeros and no limit cases.
22        if (!isLeadingZero && !isLimit && memo[position][previousDigit] !== -1) {
23            return memo[position][previousDigit];
24        }
25
26        let count = 0;
27        const upperLimit = isLimit ? +num[position] : 9;
28
29        // Try all possible next digits.
30        for (let digit = 0; digit <= upperLimit; digit++) {
31            if (digit === 0 && isLeadingZero) {
32                // Skip leading zeroes after the first digit.
33                count += dfs(position + 1, previousDigit, true, isLimit && digit === upperLimit);
34            } else if (previousDigit === -1 || Math.abs(previousDigit - digit) === 1) {
35                // Check that the number is a stepping number (difference between adjacent digits is 1).
36                count += dfs(position + 1, digit, false, isLimit && digit === upperLimit);
37            }
38            count %= MODULUS;
39        }
40
41        // Memoize the result if not leading zero and not at the limit.
42        if (!isLeadingZero && !isLimit) {
43            memo[position][previousDigit] = count;
44        }
45
46        return count;
47    };
48
49    // Find the number of stepping numbers up to the 'high' value.
50    let num = high;
51    const countHigh = dfs(0, -1, true, true);
52
53    // Adjust 'low' to include it in the range and then find the number up to 'low'.
54    num = (BigInt(low) - 1n).toString();
55    memo = Array(maxDigits + 1).fill(0).map(() => Array(10).fill(-1));
56    const countLow = dfs(0, -1, true, true);
57
58    // Calculate the number of stepping numbers between 'low' and 'high' by subtracting counts.
59    return (countHigh - countLow + MODULUS) % MODULUS;
60}
61

Time and Space Complexity

The given Python code defines a method countSteppingNumbers to find the count of stepping numbers between two numbers, low and high. A stepping number is a number whose adjacent digits have a difference of 1. The code uses a depth-first search (DFS) strategy with memoization (via @cache) to explore all valid stepping numbers within the given range.

Time Complexity

The time complexity of the algorithm involves analyzing the DFS calls. In the worst case, the DFS explores every digit position from [0, length of num) for each valid stepping number sequence:

The number of digit positions corresponds to the length of high, as num is initially set to high.
At each digit position, pos, there are at most 10 choices (digits from 0 to 9) except when the limit is True, which restricts the choices to up + 1.
Due to memoization, each unique state is only computed once. A state is defined by the pos, the previous digit pre, whether we are leading with a zero lead, and whether we are at the limit limit.
There are len(num) positions, 10 possible values for pre (including the initial -1), and two possible boolean values for both lead and limit.

The total unique states are len(num) * 10 * 2 * 2.

Given that len(num) equals the length of the string representation of high, denoted as L, the time complexity of the algorithm is O(L * 10 * 2 * 2), which simplifies to O(L) since 10 * 2 * 2 is a constant.

Space Complexity

The space complexity is primarily determined by the storage of the memoization cache and the call stack due to recursion:

The memoization cache stores results for each unique state. Since the total unique states are len(num) * 10 * 2 * 2, the space usage for memoization is O(L * 10 * 2 * 2), which simplifies to O(L).
The DFS recursion depth is bounded by the length of num, which is O(L).

Therefore, considering both the memoization cache and the recursion call stack, the space complexity of the algorithm is also O(L).

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

dp[i] = dp[i] + 1

dp[i] = dp[i] + dp[i - 1]

dp[i] = (dp[i] + dp[j] + 1) for j in 0 to i

dp[i] = max(dp[i], dp[j] + 1) for j in 0 to i

I don't know