Count Stepping Numbers in Range

Hard

Asked by:

17 views

Topics:

Dynamic ProgrammingRecursion

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⁹ + 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) < 10¹⁰⁰
1 <= low.length, high.length <= 100
low and high consist of only digits.
low and high don't have any leading zeros.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the low and high input values?
Are 'low' and 'high' inclusive or exclusive when determining the range?
How should I handle the case where low is greater than high?
Should I return the count as an integer or a long?
Are leading zeros allowed in the stepping numbers? For example, is '012' a valid stepping number?

Brute Force Solution

Approach

The brute force method for counting stepping numbers in a range is straightforward: we will check every number within the given range. For each number, we'll determine if it's a stepping number, and if so, we'll increase our count.

Here's how the algorithm would work step-by-step:

Start with the first number in the given range.
Check if the current number is a stepping number (meaning the difference between adjacent digits is always one).
If it is, increase the count of stepping numbers.
Move to the next number in the range.
Repeat steps two through four until you've checked every number up to the end of the range.
The final count represents the total number of stepping numbers within the specified range.

Code Implementation

def count_stepping_numbers_brute_force(low_range, high_range):
    stepping_number_count = 0
    for current_number in range(low_range, high_range + 1):
        if is_stepping_number(current_number):

            # Increment if the number is a stepping number
            stepping_number_count += 1

    return stepping_number_count

def is_stepping_number(number):
    number_string = str(number)

    # A single-digit number is always a stepping number
    if len(number_string) == 1:
        return True

    for index in range(len(number_string) - 1):
        digit1 = int(number_string[index])
        digit2 = int(number_string[index + 1])

        # Check if the absolute difference is not equal to 1
        if abs(digit1 - digit2) != 1:
            return False

    # Reached here if all adjacent digits differ by 1
    return True

Big(O) Analysis

Time Complexity

O((b-a) * log10(b)) – The brute force algorithm iterates through each number from 'a' to 'b', where the number of iterations is directly proportional to (b-a), representing the size of the range. For each number, the algorithm checks if it's a stepping number by examining its digits. The number of digits in a number 'n' is approximately log10(n). Therefore, for each number in the range, we perform approximately log10(b) operations (as b is the upper bound of the range, it will have the largest number of digits within that range). The total operations approximate (b-a) * log10(b), so the time complexity is O((b-a) * log10(b)).

Space Complexity

O(1) – The brute force method described iterates through numbers within the given range and checks each number individually. The algorithm does not use any auxiliary data structures such as lists, hashmaps, or additional arrays to store intermediate results or track visited numbers. It only uses a few constant space variables like counters and boolean flags to perform the stepping number check, whose memory consumption remains constant irrespective of the input range size (N). Therefore, the space complexity is O(1).

Optimal Solution

Approach

The best way to count stepping numbers within a range is to build them systematically. We explore all possible stepping numbers, but we do so in a way that avoids unnecessary calculations and efficiently finds all the ones within our given range.

Here's how the algorithm would work step-by-step:

Think of stepping numbers like a tree, where each node is a digit, and you can only go to the next digit if it's one more or one less than the current digit.
Start with each single digit number (0 through 9) because they are all stepping numbers.
From each of those single digit numbers, explore the possible next digits following the stepping number rule (plus or minus one). For example, from '2' you can explore '1' and '3'.
Continue building these stepping numbers, but only keep the ones that fall within the specified range.
Stop exploring a number if it goes outside the range or if it has become too long (longer than the upper limit of the range).
Count how many stepping numbers you created that are within the desired range; this is the final answer.

Code Implementation

def count_stepping_numbers_in_range(low_range, high_range):
    stepping_numbers_count = 0

    def stepping_number_dfs(current_number):
        nonlocal stepping_numbers_count

        if low_range <= current_number <= high_range:
            stepping_numbers_count += 1

        if current_number > high_range:
            return

        last_digit = current_number % 10

        # Explore the next possible digits
        next_digit_plus = last_digit + 1
        next_digit_minus = last_digit - 1

        # Explore the next stepping number by adding one to the last digit
        if next_digit_plus <= 9:

            next_number = current_number * 10 + next_digit_plus

            stepping_number_dfs(next_number)

        # Explore the next stepping number by subtracting one from the last digit
        if next_digit_minus >= 0:

            next_number = current_number * 10 + next_digit_minus

            stepping_number_dfs(next_number)

    # Single digit numbers are always stepping numbers
    for start_digit in range(10):

        stepping_number_dfs(start_digit)

    # Remove 0 if it's outside the range as it was counted in the loop
    if low_range > 0 and 0 in range(low_range, high_range+1):
        stepping_numbers_count -= 1

    return stepping_numbers_count

Big(O) Analysis

Time Complexity

O(10 * 2^N) – The algorithm explores stepping numbers starting from each of the 10 single digits (0-9). For each starting digit, it generates stepping numbers by either incrementing or decrementing the last digit. In the worst case, up to a length equivalent to the number of digits in the upper bound (N), this can result in a branching factor of 2 at each level (except when the digit is 0 or 9, which have only one option). Thus, from each starting digit we potentially explore 2^N possible stepping numbers. Since we begin with 10 digits, the overall complexity is approximately 10 * 2^N, where N represents the number of digits in the upper bound of the range.

Space Complexity

O(10^M) – The space complexity is dominated by the maximum number of stepping numbers generated during the exploration, where M is the number of digits in the upper bound of the range. The algorithm starts exploring from single-digit numbers (0-9) and extends them, effectively building a tree-like structure of stepping numbers. In the worst case, it might explore all possible stepping numbers up to the length of the upper bound, which can grow exponentially. Although some generated stepping numbers may be pruned as they exceed the bounds, the potential size of stepping numbers that need to be stored for exploration purposes determines the space required, which depends on the upper bound of the range (represented by the number of digits). Considering a stepping number with digits from 0-9, and with the number of digits M, the count can grow close to 10^M so that is the space occupied.

Edge Cases

Case	How to Handle
Low and High are equal	Check if the single number is a stepping number.
Low is greater than High	Return 0 since there are no numbers in that range.
Low and High are 0	Return 1 since 0 is considered a stepping number.
Large range between Low and High (e.g., 1 to 10^9)	BFS/DFS solution should explore only stepping numbers, making it efficient even for a large range.
Integer overflow during stepping number generation	Use a data type like 'long' to handle potentially large stepping numbers, and check that generated numbers do not exceed High.
Low and/or High are negative	Consider the absolute values if stepping numbers are defined as such, otherwise return zero since the problem definition only covers positives.
Low starts with 0, and High is greater than 0	Treat 0 as a stepping number, and the solution must only count numbers in the inclusive range of Low to High.
All single-digit numbers are stepping numbers	Ensure the code handles single-digit numbers correctly and that no duplicates are counted in the generation process.

Low and High are equal

How to Handle:

Check if the single number is a stepping number.

Low is greater than High

How to Handle:

Return 0 since there are no numbers in that range.

Low and High are 0

How to Handle:

Return 1 since 0 is considered a stepping number.

Large range between Low and High (e.g., 1 to 10^9)

How to Handle:

BFS/DFS solution should explore only stepping numbers, making it efficient even for a large range.

Integer overflow during stepping number generation

How to Handle:

Use a data type like 'long' to handle potentially large stepping numbers, and check that generated numbers do not exceed High.

Low and/or High are negative

How to Handle:

Consider the absolute values if stepping numbers are defined as such, otherwise return zero since the problem definition only covers positives.

Low starts with 0, and High is greater than 0

How to Handle:

Treat 0 as a stepping number, and the solution must only count numbers in the inclusive range of Low to High.

All single-digit numbers are stepping numbers

How to Handle:

Ensure the code handles single-digit numbers correctly and that no duplicates are counted in the generation process.