Last Updated: 16 Mar, 2021
Stepping Numbers
Moderate
Asked in company
You are given two positive integers ‘L’ and ‘R’. Find all the Stepping Numbers in the range [L, R].
A positive integer is called a Stepping Number if the adjacent digits have a difference of 1. For example, 121 is a Stepping Number because |1-2| = 1 and |2 -1| = 1. All single-digit integers will also be considered as Stepping Numbers.
You should return a list of Stepping Numbers between ‘L’ and ‘R’ (inclusive) in the increasing order.
For Example:
Consider L = 10, R = 13.
Then, all integers in range [10, 13] are 10, 11, 12, 13.
We can say, that 10 is a stepping number because |1 - 0| = 1.
11 is not a stepping number because |1 - 1| = 0.
12 is a stepping number because |1 - 2| = 1.
13 is not a stepping number because |1 - 3| = 2.
Thus, we should return a list [10, 12].
Input format:
The first line of input contains an integer ‘T’ denoting the number of test cases. Then, ‘T’ test cases follow.
The first and the only line of each test case consist of two space-separated integers ‘L’ and ‘R’ respectively.
Output format :
For each test case, if there are ‘K’ stepping numbers between ‘L’ and ‘R’, then print a single line consisting of ‘K’ space-separated integers representing Stepping Numbers between ‘L’ and ‘R’ in increasing order.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= L <= 10^8
1 <= R <= 10^8
R >= L
Time Limit: 1 second
Approaches
This approach is straightforward, we iterate over all integers from ‘L’ to ‘R’ and for each integer, we check whether it is a stepping number or not. If the integer is a stepping number then we will append it in the resultant list. We can check whether a number is a stepping number or not by simply iterating over its digit as described in the algorithm mentioned below.
Algorithm
- Create an empty list of integers ‘result’.
- Run a loop where ‘i’ ranges from ‘L’ to ‘R’ and for each ‘i’ do the following:
- Initialize an integer variable curNum := i.
- If curNum < 10, then append curNum in the result and skip the current iteration.
- Initialize an integer variable nextDigit:= curNum % 10 and then do curNum:= curNum / 10.
- Initialize a boolean variable flag:= true.
- Run a while loop till curNum > 0 and in each iteration do the following
- If abs(curNum % 10 - nextDigit) != 1, then do flag:= false and break the loop
- Otherwise, do nextDigit:= curNum % 10 and curNum: = curNum /= 10.
- If flag = true, then append ‘i’ in ‘result’.
- Return result.
Consider a directed graph where every node represents a stepping number. There will be a directed edge from node ‘u’ to ‘v’, if the stepping number ‘u’ can be converted into stepping number ‘v’ by adding one more digit. i.e there will be directed edge from ‘u’ to ‘v if either:
v = u*10 + u%10 -1 (u % 10 != 0)
or v = u*10 + u % 10 + 1 (u % 10!= 9)
After this, we can solve this problem using Depth-First Search (DFS) or Breadth-First Search (BFS) algorithm. We have described a DFS based algorithm below, The problem can be solved similarly using BFS similarly.
Algorithm
- Create an empty list of integers ‘result’.
- Create a recursive function dfs(curNum) and do the following -:
- If curNum <= R or curNum >= ‘L’ then append cuNum in result.
- If curNum > R or curNum = 0 then return.
- Initialize an integer variable lastDigit:= curNum % 10.
- If lastDigit != 0, then call dfs(curNum*10 + lastDigit - 1).
- If lastDigit != 9, then call dfs(curNum*10 + lastDigit + 1).
- Run a loop where ‘i’ ranges from 1 to 9 and for each ‘i’ call dfs(i).
- Return result.