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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Stepping Numbers in Range

Difficulty: Hard

Problem Description

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 10^9 + 7. A stepping number should not have a leading zero.

Key Insights

  • Stepping numbers are formed by digits that differ by 1.
  • The problem can be approached using a breadth-first search (BFS) or depth-first search (DFS) to generate all possible stepping numbers.
  • The range of numbers can be very large (up to 10^100), so direct iteration is not feasible.
  • We can construct stepping numbers digit by digit, ensuring that we remain within the bounds defined by low and high.

Space and Time Complexity

Time Complexity: O(10^n), where n is the number of digits in the largest stepping number generated.
Space Complexity: O(n), where n is the depth of the recursion stack or the width of the BFS queue.

Solution

The solution utilizes a breadth-first search (BFS) approach to generate all possible stepping numbers starting from each digit (1 to 9). For each number generated, we check if it lies within the specified range [low, high]. We ensure that numbers do not have leading zeros and we adhere to the stepping number condition.

  1. Start BFS from each digit from 1 to 9.
  2. For each number, generate new numbers by appending digits that differ by 1 from the last digit of the current number.
  3. Count how many of the generated numbers are within the range defined by low and high.
  4. Return the total count modulo 10^9 + 7.

Code Solutions

def countSteppingNumbers(low: str, high: str) -> int:
    from collections import deque
    
    MOD = 10**9 + 7
    low_num = int(low)
    high_num = int(high)
    count = 0

    # BFS to generate stepping numbers
    queue = deque(range(1, 10))  # Start from digits 1 to 9

    while queue:
        num = queue.popleft()
        
        if low_num <= num <= high_num:
            count += 1
        
        last_digit = num % 10
        
        # Append the next possible digits (last_digit-1 and last_digit+1)
        if last_digit > 0:  # last_digit - 1
            next_num = num * 10 + (last_digit - 1)
            if next_num <= high_num:
                queue.append(next_num)
        if last_digit < 9:  # last_digit + 1
            next_num = num * 10 + (last_digit + 1)
            if next_num <= high_num:
                queue.append(next_num)

    return count % MOD
← Back to All Questions