# Count Stepping Numbers in Range **Difficulty:** HARD [External](https://leetcode.com/problems/count-stepping-numbers-in-range) Canonical: https://scaleengineer.com/dsa/problems/count-stepping-numbers-in-range **Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming) **Data structures:** String --- ## Problem Given two positive integers `low` and `high` represented as strings, find the count of **stepping numbers** in the inclusive range `[low, high]`. A **stepping number** is an integer such that all of its adjacent digits have an absolute difference of **exactly** `1`. Return _an integer denoting the count of stepping numbers in the inclusive range_ `[low, high]`_._ Since the answer may be very large, return it **modulo** `109 + 7`. **Note:** A stepping number should not have a leading zero. **Example 1:** **Input:** low = "1", high = "11" **Output:** 10 **Explanation:** The stepping numbers in the range [1,11] are 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10. There are a total of 10 stepping numbers in the range. Hence, the output is 10. **Example 2:** **Input:** low = "90", high = "101" **Output:** 2 **Explanation:** The stepping numbers in the range [90,101] are 98 and 101. There are a total of 2 stepping numbers in the range. Hence, the output is 2. **Constraints:** * `1 <= int(low) <= int(high) < 10100` * `1 <= low.length, high.length <= 100` * `low` and `high` consist of only digits. * `low` and `high` don't have any leading zeros. # Approaches ## BFS to Generate Stepping Numbers This approach involves generating all stepping numbers starting from single-digit numbers and expanding them one digit at a time. We can use a Breadth-First Search (BFS) to generate these numbers in increasing order of their number of digits, and then by value. We stop generating when the numbers exceed the `high` bound. **Time:** O(S(L_high)) where S(L_high) is the number of stepping numbers with at most L_high digits (length of `high`). The number of stepping numbers grows exponentially with the number of digits, making this approach too slow for the given constraints. · **Space:** O(S(L_high)) where S(L_high) is the number of stepping numbers up to the number of digits in `high`. The space required to store the numbers in the queue can become very large. **Pros:** Conceptually simpler to understand and implement than digit dynamic programming.; Works correctly for smaller ranges where `high` is not excessively large. **Cons:** Inefficient for large `high` (up to 100 digits) as the number of stepping numbers grows exponentially.; High memory usage for the queue, which can lead to memory limit errors.; Requires `BigInteger` operations, which are slower than operations on primitive types. ### Explanation The core idea is to build stepping numbers digit by digit. We can start with all single-digit numbers (1-9) as the initial set of stepping numbers. We use a queue for the BFS process. Initially, the queue contains all single-digit numbers. In each step of the BFS, we dequeue a number `u`. If `u` is within the given range `[low, high]`, we count it. Then, we generate new stepping numbers by appending a digit to `u`. Let the last digit of `u` be `last_d`. The new digit can be `last_d - 1` or `last_d + 1`, provided it's a valid digit (0-9). For example, if `u` is 21, `last_d` is 1. We can append 0 or 2. The new numbers are 210 and 212. These newly generated numbers are enqueued for further processing, but only if they do not exceed the `high` bound. Since the numbers can be very large (up to 100 digits), we should use a data type that can handle them, such as `BigInteger` in Java. The process continues until the queue is empty or all remaining numbers in the queue are greater than `high`. ```java import java.math.BigInteger; import java.util.LinkedList; import java.util.Queue; class Solution { public int countSteppingNumbers(String low, String high) { BigInteger lowNum = new BigInteger(low); BigInteger highNum = new BigInteger(high); int count = 0; final int MOD = 1_000_000_007; Queue q = new LinkedList<>(); for (long i = 1; i <= 9; i++) { q.add(BigInteger.valueOf(i)); } while (!q.isEmpty()) { BigInteger curr = q.poll(); if (curr.compareTo(highNum) > 0) { continue; } if (curr.compareTo(lowNum) >= 0) { count = (count + 1) % MOD; } int lastDigit = curr.mod(BigInteger.TEN).intValue(); if (lastDigit > 0) { BigInteger nextNum = curr.multiply(BigInteger.TEN).add(BigInteger.valueOf(lastDigit - 1)); if (nextNum.compareTo(highNum) <= 0) { q.add(nextNum); } } if (lastDigit < 9) { BigInteger nextNum = curr.multiply(BigInteger.TEN).add(BigInteger.valueOf(lastDigit + 1)); if (nextNum.compareTo(highNum) <= 0) { q.add(nextNum); } } } return count; } } ``` ### Algorithm - Initialize a queue and add all single-digit numbers (1 to 9) to it. - Initialize a counter `count` to 0. - Convert `low` and `high` strings to a type that supports large numbers, like `BigInteger` in Java, for easy comparison. - While the queue is not empty: - Dequeue a number `currentNum`. - If `currentNum` is greater than `high`, we can prune this path as all subsequent numbers generated from it will also be greater. - If `currentNum` is within the range `[low, high]`, increment `count`. - Get the last digit of `currentNum`: `lastDigit = currentNum % 10`. - If `lastDigit > 0`, form `nextNum1 = currentNum * 10 + (lastDigit - 1)`. If `nextNum1 <= high`, enqueue it. - If `lastDigit < 9`, form `nextNum2 = currentNum * 10 + (lastDigit + 1)`. If `nextNum2 <= high`, enqueue it. - Return `count`. ## Digit Dynamic Programming This is the most efficient approach for this type of problem with large number constraints. The core idea is to count the number of stepping numbers up to `high` and subtract the count of stepping numbers up to `low - 1`. This can be formulated as `count(high) - count(low) + isStepping(low)`. The `count(N)` function, which counts stepping numbers up to a number `N`, is implemented using digit dynamic programming. **Time:** O(L * 10 * 2 * 2 * 10), where L is the length of the number string. The number of states in the DP is `L * |prevDigit| * |isTight| * |isLeadingZero|`. `|prevDigit|` is 11 (0-9 and an initial state), `|isTight|` is 2, `|isLeadingZero|` is 2. For each state, we iterate at most 10 times for the next digit. This simplifies to O(L). The total time is dominated by `count(high)` and `count(low)`. · **Space:** O(L * 11 * 2 * 2) for the memoization table, where L is the length of the number string (max 100). This simplifies to O(L). **Pros:** Highly efficient and guaranteed to pass within the time limits for very large numbers (up to 100 digits).; It is a standard and powerful technique for problems of the type 'count numbers up to N with property X'. **Cons:** The logic can be complex to understand and implement correctly, especially handling the state transitions for `isTight` and `isLeadingZero` flags. ### Explanation We design a recursive function, let's call it `dfs`, that counts valid numbers from a given state. The state needs to capture all information required to decide the next digits without violating any constraints. We use memoization to store the results of `dfs` for each state to avoid re-computation. The state for our `dfs` function will be `(index, prevDigit, isTight, isLeadingZero)`: - `index`: The current digit position we are filling (from left, 0-indexed). - `prevDigit`: The value of the previously placed digit. We can use a special value (e.g., 10) to indicate that no digit has been placed yet. - `isTight`: A boolean flag. It's `true` if we are restricted to the digits of the upper bound string `N`. For example, if `N = "854"` and we have placed `85`, the next digit can only be from 0 to 4. If we had placed `84`, the next digit could be 0-9. - `isLeadingZero`: A boolean flag to handle leading zeros. A number cannot start with a zero (unless it's the number 0 itself). This flag helps us enforce this rule. The main logic is to calculate `count(high)` and `count(low-1)`. A simpler way to get the count in `[low, high]` is `(count(high) - count(low) + isLowSteppingNumber)`. The `count(N)` function will call `dfs(N_str, 0, 10, true, true)`. This counts stepping numbers in `[0, N]`. Since the problem asks for positive integers, we subtract 1 to exclude 0. ```java import java.util.Arrays; class Solution { private static final int MOD = 1_000_000_007; private String s; private int[][][][] memo; private int dfs(int index, int prevDigit, boolean isTight, boolean isLeadingZero) { if (index == s.length()) { return 1; // A valid number is formed } if (memo[index][prevDigit][isTight ? 1 : 0][isLeadingZero ? 1 : 0] != -1) { return memo[index][prevDigit][isTight ? 1 : 0][isLeadingZero ? 1 : 0]; } long ans = 0; int upperBound = isTight ? (s.charAt(index) - '0') : 9; for (int digit = 0; digit <= upperBound; digit++) { boolean newTight = isTight && (digit == upperBound); if (isLeadingZero) { if (digit == 0) { ans = (ans + dfs(index + 1, 10, newTight, true)) % MOD; } else { ans = (ans + dfs(index + 1, digit, newTight, false)) % MOD; } } else { if (Math.abs(digit - prevDigit) == 1) { ans = (ans + dfs(index + 1, digit, newTight, false)) % MOD; } } } return memo[index][prevDigit][isTight ? 1 : 0][isLeadingZero ? 1 : 0] = (int) ans; } private int count(String numStr) { this.s = numStr; this.memo = new int[s.length()][11][2][2]; for (int[][][] a : memo) { for (int[][] b : a) { for (int[] c : b) { Arrays.fill(c, -1); } } } // dfs counts numbers in [0, s], including 0. // We want count in [1, s], so subtract 1 for 0. return (dfs(0, 10, true, true) - 1 + MOD) % MOD; } private boolean isStepping(String s) { for (int i = 0; i < s.length() - 1; i++) { if (Math.abs(s.charAt(i) - s.charAt(i + 1)) != 1) { return false; } } return true; } public int countSteppingNumbers(String low, String high) { int countHigh = count(high); int countLow = count(low); int ans = (countHigh - countLow + MOD) % MOD; if (isStepping(low)) { ans = (ans + 1) % MOD; } return ans; } } ``` ### Algorithm - The final answer is calculated as `(count(high) - count(low) + (isStepping(low) ? 1 : 0)) % MOD`. - Implement a function `count(String s)` which calculates the number of stepping numbers between 1 and `s` (inclusive). - `count(s)` is implemented using a recursive helper function `dfs` with memoization. The result of `count(s)` is `(dfs(s, ...) - 1 + MOD) % MOD`. The `-1` is to exclude the number 0, which our `dfs` implementation counts. - The `dfs(s, index, prevDigit, isTight, isLeadingZero)` function is defined as follows: - **Base Case:** If `index == s.length()`, we have successfully formed a valid number. Return 1. - **Memoization:** Check if the state `(index, prevDigit, isTight, isLeadingZero)` has been computed. If so, return the stored value. - **Transitions:** Loop through possible digits for the current `index`. The upper limit for the digit is `s.charAt(index) - '0'` if `isTight` is true, otherwise it's 9. - For each `digit`: - If `isLeadingZero` is true: - If `digit` is 0, we continue with leading zeros: recurse with `dfs(..., isLeadingZero=true)`. - If `digit` is non-zero, this is the first digit. Recurse with `dfs(..., isLeadingZero=false)`. - If `isLeadingZero` is false: - Check if `abs(digit - prevDigit) == 1`. If it is, recurse with `dfs(...)`. - Sum up the results from recursive calls (modulo `MOD`). - Store the result in the memoization table and return it. - The initial call to the helper function is `dfs(s, 0, 10, true, true)`, where `prevDigit=10` is a sentinel value for the initial state. - Implement a simple helper `isStepping(String s)` to check if `low` itself is a stepping number. # Solutions ### Java ```java import java.math.BigInteger ; class Solution { private final int mod = ( int ) 1 e9 + 7 ; private String num ; private Integer [][] f ; public int countSteppingNumbers ( String low , String high ) { f = new Integer [ high . length () + 1 ][ 10 ]; num = high ; int a = dfs ( 0 , - 1 , true , true ); f = new Integer [ high . length () + 1 ][ 10 ]; num = new BigInteger ( low ). subtract ( BigInteger . ONE ). toString (); int b = dfs ( 0 , - 1 , true , true ); return ( a - b + mod ) % mod ; } private int dfs ( int pos , int pre , boolean lead , boolean limit ) { if ( pos >= num . length ()) { return lead ? 0 : 1 ; } if (! lead && ! limit && f [ pos ][ pre ] != null ) { return f [ pos ][ pre ]; } int ans = 0 ; int up = limit ? num . charAt ( pos ) - '0' : 9 ; for ( int i = 0 ; i <= up ; ++ i ) { if ( i == 0 && lead ) { ans += dfs ( pos + 1 , pre , true , limit && i == up ); } else if ( pre == - 1 || Math . abs ( pre - i ) == 1 ) { ans += dfs ( pos + 1 , i , false , limit && i == up ); } ans %= mod ; } if (! lead && ! limit ) { f [ pos ][ pre ] = ans ; } return ans ; } } ``` ### CPP ```cpp class Solution { public: int countSteppingNumbers(string low, string high) { const int mod = 1e9 + 7; int m = high.size(); int f[m + 1][10]; memset(f, -1, sizeof(f)); string num = high; function dfs = [&](int pos, int pre, bool lead, bool limit) { if (pos >= num.size()) { return lead ? 0 : 1; } if (!lead && !limit && f[pos][pre] != -1) { return f[pos][pre]; } int up = limit ? num[pos] - '0' : 9; int ans = 0; for (int i = 0; i <= up; ++i) { if (i == 0 && lead) { ans += dfs(pos + 1, pre, true, limit && i == up); } else if (pre == -1 || abs(pre - i) == 1) { ans += dfs(pos + 1, i, false, limit && i == up); } ans %= mod; } if (!lead && !limit) { f[pos][pre] = ans; } return ans; }; int a = dfs(0, -1, true, true); memset(f, -1, sizeof(f)); for (int i = low.size() - 1; i >= 0; --i) { if (low[i] == '0') { low[i] = '9'; } else { low[i] -= 1; break; } } num = low; int b = dfs(0, -1, true, true); return (a - b + mod) % mod; } }; ``` ### Python ```python class Solution: def countSteppingNumbers(self, low: str, high: str) -> int: @ cache def dfs(pos: int, pre: int, lead: bool, limit: bool) -> int: if pos >= len(num): return int(not lead) up = int(num[pos]) if limit else 9 ans = 0 for i in range(up + 1): if i == 0 and lead: ans += dfs(pos + 1, pre, True, limit and i == up) elif pre == - 1 or abs(i - pre) == 1: ans += dfs(pos + 1, i, False, limit and i == up) return ans % mod mod = 10 ** 9 + 7 num = high a = dfs(0, - 1, True, True) dfs . cache_clear() num = str(int(low) - 1) b = dfs(0, - 1, True, True) return (a - b) % mod ```