We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Stepping Numbers in Range

Number: 2921

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given two positive integers low and high represented as strings, count the number of stepping numbers in the inclusive range [low, high]. A stepping number is an integer where every two adjacent digits have an absolute difference of exactly 1. Since the answer may be huge, return it modulo 10^9+7. Note that a stepping number should not have a leading zero.

Key Insights

  • Use digit dynamic programming (digit DP) to count numbers up to a given bound that satisfy the stepping constraints.
  • The DP state keeps track of the current position, if we have “started” (i.e. chosen a non‐zero digit) so that we avoid leading zeros, the last chosen digit (to enforce the adjacent digits’ difference rule), and whether the current prefix is tight (equal to the bound’s prefix).
  • Count stepping numbers up to high and subtract the count up to (low - 1) to get the answer in [low, high].
  • A helper function is needed to subtract one from the string representing a number.

Space and Time Complexity

Time Complexity: O(N * 11 * 2 * 2) where N is the number of digits (~100), due to the DP state dimensions. Space Complexity: O(N * 11 * 2 * 2) for the memoization cache.

Solution

We solve the problem using a digit DP approach. The idea is to write a recursive function dp(pos, last, tight, started) where:

  • pos is the current index in the number string.
  • last is the last digit placed (only defined when started is true; use a dummy value such as -1 when not started).
  • tight is a flag indicating if the digits placed so far are exactly equal to the prefix of the bound.
  • started tells us if we have started forming the number (to avoid counting numbers with leading zeros).

When the number is not started, we have the option to "skip" by placing a 0 and not starting the actual number (thus counting numbers of smaller length). Once we have started, each next digit must be either last-1 or last+1 (if within 0–9) to satisfy the stepping property.

To count numbers in the inclusive range [low, high], we create a helper function countUpTo(bound) that returns the count of stepping numbers ≤ bound (excluding the “0” case if it never gets started). Finally, we compute answer = (countUpTo(high) - countUpTo(low - 1)) mod (10^9+7).

Tricks and gotchas:

  • Correctly manage the "started" state to avoid counting numbers with leading zeros.
  • Handle the "tight" condition so that at each step the choices of digits are limited by the bound.
  • Carefully implement string subtraction to decrement the low bound by 1.

Data structures used include recursion with memoization (DP table) that caches intermediate results. The algorithm iterates over digit positions up to the length of the bound, making it efficient even for numbers with up to 100 digits.

Code Solutions

Below are implementations in Python, JavaScript, C++, and Java with line-by-line comments.

MOD = 10**9 + 7

def count_stepping(bound: str) -> int:
    n = len(bound)
    # dp(pos, last, tight, started) returns the count of valid numbers from position pos
    from functools import lru_cache
    @lru_cache(maxsize=None)
    def dp(pos, last, tight, started):
        # Base case: if we've processed all positions
        if pos == n:
            # Count the number only if we have started (i.e. the number is not all leading zeros)
            return 1 if started else 0
        count = 0
        # Current upper limit for digit at pos if we are in a tight state
        limit = int(bound[pos]) if tight else 9
        # Iterate over all digit choices for current position
        for d in range(0, limit + 1):
            next_tight = tight and (d == limit)
            # If we haven't started the number yet
            if not started:
                if d == 0:
                    # Remain in not-started so that we can pick a non-zero later
                    count = (count + dp(pos + 1, -1, next_tight, False)) % MOD
                else:
                    # Start the number with non-zero digit d
                    count = (count + dp(pos + 1, d, next_tight, True)) % MOD
            else:
                # Already started: enforce stepping property, allowed digit must be last-1 or last+1
                # Only consider next digit if it equals to permitted stepping value
                if d == last - 1 or d == last + 1:
                    count = (count + dp(pos + 1, d, next_tight, True)) % MOD
        return count

    return dp(0, -1, True, False)

def subtract_one(num_str: str) -> str:
    # Helper function to subtract 1 from a number represented as a string.
    num_list = list(num_str)
    i = len(num_list) - 1
    while i >= 0:
        if num_list[i] == '0':
            num_list[i] = '9'
            i -= 1
        else:
            num_list[i] = str(int(num_list[i]) - 1)
            break
    # Remove leading zeros if necessary.
    result = ''.join(num_list).lstrip('0')
    return result if result != "" else "0"

def countSteppingNumbers(low: str, high: str) -> int:
    countHigh = count_stepping(high)
    # Compute count for numbers smaller than low, i.e. count numbers ≤ (low - 1)
    low_minus_one = subtract_one(low)
    countLow = count_stepping(low_minus_one) if low_minus_one != "0" else 0
    result = (countHigh - countLow) % MOD
    return result

# Example usage:
print(countSteppingNumbers("1", "11"))   # Expected output: 10
print(countSteppingNumbers("90", "101")) # Expected output: 2
← Back to All Questions