Generate stepping numbers upto a given number N

Question

A number is called a stepping number if all adjacent digits in the number have an absolute difference of 1.

Examples of stepping numbers :- 0,1,2,3,4,5,6,7,8,9,10,12,21,23,...

I have to generate stepping numbers upto a given number N. The numbers generated should be in order.

I used the simple method of moving over all the numbers upto N and checking if it is stepping number or not. My teacher told me it is brute force and will take more time. Now, I have to optimize my approach.

Any suggestions.

Have you tried using BFS? Store the starting stepping numbers first in a queue. Pop them and add new stepping numbers. See the link in my answer. — Adarsh Anurag
@AdarshAnurag Depth First Search (DFS) would work just as well, and is simpler to implement. — john
but using DFS, numbers cannot be generated in ascending order. — Adarsh Anurag
@AdarshAnurag True, but I see no requirement to provide the numbers in ascending order. — john
@AdarshAnurag, Thank you for help. I never knew BFS and DFS can be applied here. — user11799835

Adarsh Anurag Adarsh Anurag · Accepted Answer · 2019-07-18T08:22:31

Stepping numbers can be generated using Breadth First Search like approach.

Example to find all the stepping numbers from 0 to N

-> 0 is a stepping Number and it is in the range so display it. -> 1 is a Stepping Number, find neighbors of 1 i.e., 10 and 12 and push them into the queue

How to get 10 and 12?

Here U is 1 and last Digit is also 1

V = 10 + 0 = 10 ( Adding lastDigit - 1 )

V = 10 + 2 = 12 ( Adding lastDigit + 1 )

Then do the same for 10 and 12 this will result into 101, 123, 121 but these Numbers are out of range. Now any number transformed from 10 and 12 will result into a number greater than 21 so no need to explore their neighbors.

-> 2 is a Stepping Number, find neighbors of 2 i.e. 21, 23. -> generate stepping numbers till N.

The other stepping numbers will be 3, 4, 5, 6, 7, 8, 9.

C++ code to do generate stepping numbers in a given range:

#include<bits/stdc++.h> 
using namespace std; 

// Prints all stepping numbers reachable from num 
// and in range [n, m] 
void bfs(int n, int m) 
{ 
    // Queue will contain all the stepping Numbers 
    queue<int> q; 

    for (int i = 0 ; i <= 9 ; i++) 
        q.push(i);

    while (!q.empty()) 
    { 
        // Get the front element and pop from the queue 
        int stepNum = q.front(); 
        q.pop(); 

        // If the Stepping Number is in the range 
        // [n, m] then display 
        if (stepNum <= m && stepNum >= n) 
            cout << stepNum << " "; 

        // If Stepping Number is 0 or greater than m, 
        // need to explore the neighbors 
        if (stepNum == 0 || stepNum > m) 
            continue; 

        // Get the last digit of the currently visited 
        // Stepping Number 
        int lastDigit = stepNum % 10; 

        // There can be 2 cases either digit to be 
        // appended is lastDigit + 1 or lastDigit - 1 
        int stepNumA = stepNum * 10 + (lastDigit- 1); 
        int stepNumB = stepNum * 10 + (lastDigit + 1); 

        // If lastDigit is 0 then only possible digit 
        // after 0 can be 1 for a Stepping Number 
        if (lastDigit == 0) 
            q.push(stepNumB); 

        //If lastDigit is 9 then only possible 
        //digit after 9 can be 8 for a Stepping 
        //Number 
        else if (lastDigit == 9) 
            q.push(stepNumA); 

        else
        { 
            q.push(stepNumA); 
            q.push(stepNumB); 
        } 
    } 
}  

//Driver program to test above function 
int main() 
{ 
    int n = 0, m = 99; 

    // Display Stepping Numbers in the 
    // range [n,m] 
    bfs(n,m); 
    return 0; 
}

Visit this link. The mentioned link has both BFS and DFS approach. It will provide you with explaination and code in different languages for the above problem.

Generate stepping numbers upto a given number N

2 Answers