Stepping Numbers | A C ++ program to find all the Stepping Number from N = n to m using BFS Approach ; Prints all stepping numbers reachable from num and in range [ n , m ] ; Queue will contain all the stepping Numbers ; Get the front element and pop from the queue ; If the Stepping Number is in the range [ n , m ] then display ; If Stepping Number is 0 or greater than m , no need to explore the neighbors ; Get the last digit of the currently visited Stepping Number ; There can be 2 cases either digit to be appended is lastDigit + 1 or lastDigit - 1 ; If lastDigit is 0 then only possible digit after 0 can be 1 for a Stepping Number ; If lastDigit is 9 then only possible digit after 9 can be 8 for a Stepping Number ; Prints all stepping numbers in range [ n , m ] using BFS . ; For every single digit Number ' i ' find all the Stepping Numbers starting with i ; Driver program to test above function ; Display Stepping Numbers in the range [ n , m ]
#include <bits/stdc++.h> NEW_LINE using namespace std ; void bfs ( int n , int m , int num ) { queue < int > q ; q . push ( num ) ; while ( ! q . empty ( ) ) { int stepNum = q . front ( ) ; q . pop ( ) ; if ( stepNum <= m && stepNum >= n ) cout << stepNum << " ▁ " ; if ( num == 0 stepNum > m ) continue ; int lastDigit = stepNum % 10 ; int stepNumA = stepNum * 10 + ( lastDigit - 1 ) ; int stepNumB = stepNum * 10 + ( lastDigit + 1 ) ; if ( lastDigit == 0 ) q . push ( stepNumB ) ; else if ( lastDigit == 9 ) q . push ( stepNumA ) ; else { q . push ( stepNumA ) ; q . push ( stepNumB ) ; } } } void displaySteppingNumbers ( int n , int m ) { for ( int i = 0 ; i <= 9 ; i ++ ) bfs ( n , m , i ) ; } int main ( ) { int n = 0 , m = 21 ; displaySteppingNumbers ( n , m ) ; return 0 ; }