A Stepping Number is an integer such that all of its adjacent digits have an absolute difference of exactly 1. For example, 321 is a Stepping Number while 421 is not.
Given two integers low and high, find and return a sorted list of all the Stepping Numbers in the range [low, high] inclusive.
Example 1:
Input: low = 0, high = 21 Output: [0,1,2,3,4,5,6,7,8,9,10,12,21]
Example 2:
Input: low = 10, high = 15 Output: [10,12]
Constraints:
0 <= low <= high <= 2 * 109When 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:
Every integer from the lower endpoint through the upper endpoint is tested. A one-digit number is accepted immediately, and a longer number is accepted only when every pair of neighboring digits differs by exactly one. The accepted numbers are sorted before they are returned.
Here's how the algorithm would work step-by-step:
def find_stepping_numbers_brute_force(start_number, end_number):
stepping_numbers_result = []
# Iterate through every single number in the given range to check if it's a stepping number.
for current_number in range(start_number, end_number + 1):
number_as_string = str(current_number)
# Single-digit numbers are always stepping numbers by definition.
if len(number_as_string) <= 1:
stepping_numbers_result.append(current_number)
continue
is_stepping_number = True
# Check each pair of adjacent digits to see if they differ by exactly 1.
for digit_index in range(len(number_as_string) - 1):
first_digit = int(number_as_string[digit_index])
second_digit = int(number_as_string[digit_index + 1])
# If any pair of adjacent digits violates the stepping number rule, the number is disqualified.
if abs(first_digit - second_digit) != 1:
is_stepping_number = False
break
if is_stepping_number:
stepping_numbers_result.append(current_number)
return sorted(stepping_numbers_result)Stepping numbers are grown one digit at a time, starting from the digits one through nine. From any number, the next digit is either one below or one above its last digit, and a number already past the upper bound is not extended. Zero is added only when the lower bound allows it, and the collected numbers are sorted at the end.
Here's how the algorithm would work step-by-step:
def find_stepping_numbers(low_bound, high_bound):
result_numbers = []
if low_bound == 0:
result_numbers.append(0)
# A queue is used to build stepping numbers digit by digit in a breadth-first manner.
queue_for_generation = [digit for digit in range(1, 10)]
while queue_for_generation:
current_number = queue_for_generation.pop(0)
if low_bound <= current_number <= high_bound:
result_numbers.append(current_number)
# Stop generating longer numbers from the current one if it already exceeds the upper bound.
if current_number > high_bound:
continue
last_digit = current_number % 10
# Generate the next stepping number by appending a digit that is one less than the last digit.
if last_digit > 0:
next_number_option_one = current_number * 10 + (last_digit - 1)
if next_number_option_one <= high_bound:
queue_for_generation.append(next_number_option_one)
# Generate the next stepping number by appending a digit that is one more than the last digit.
if last_digit < 9:
next_number_option_two = current_number * 10 + (last_digit + 1)
if next_number_option_two <= high_bound:
queue_for_generation.append(next_number_option_two)
return sorted(result_numbers)| Case | How to Handle |
|---|---|
| The range contains one number that is not stepping | The scan rejects it and the digit builder never records it, so the result is empty. |
| The lower endpoint is zero | Zero is recorded immediately, and generation starts from the digits one through nine so zero is not used as a prefix. |
| Both endpoints are single digits | Every value in the range is accepted because a single digit has no neighboring pair to violate the rule. |
| Ten is inside the range and eleven is also inside | Ten is kept because its digits differ by one, and eleven is rejected because its digits are equal. |
| A longer candidate would pass the upper bound | That candidate is not kept and is not used to grow still longer numbers. |