Given a number N, the task is to print the first N Stepping Numbers.
A number is called stepping number if all adjacent digits have an absolute difference of 1. For e.g. 321 is a Stepping Number while 421 is not.
Examples:
Input: N = 7
Output: 1, 2, 3, 4, 5, 6, 7
Input: N = 14
Output: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22
Naive approach: We can start from 1 and check for every number whether they are Stepping number or not and continue till we find the K-th Stepping number.
Efficient Approach:
- Generate all possible Stepping numbers till 1000, for easy computation
- For each value of N, just print the N already computed Stepping numbers
Below is the implementation of the above approach:
C++
// C++ Program to print first N// Stepping numbers#include <bits/stdc++.h>using namespace std;// Function to generate// the Stepping numbersvoid generateSteppingNos( int x, set<int>& s){ if (x > 1e8) return; // Inserting the current // element in the set s.insert(x); // Retrieving the last digit // of the current number int last = x % 10; if (last - 1 >= 0) // Appending x-1 to // the current number generateSteppingNos( x * 10 + last - 1, s); // Appending x to // the current number generateSteppingNos( x * 10 + last, s); if (last + 1 <= 9) // Appending x+1 to // the current number generateSteppingNos( x * 10 + last + 1, s);}// Function to print// N Stepping numbersvoid NSteppingNumbers(int N){ set<int> s; for (int i = 1; i <= 9; i++) generateSteppingNos(i, s); int count = 1; // Printing N numbers from s for (auto& it : s) { if (count <= N) { cout << it << ", "; count++; } else break; }}// Driver codeint main(){ int N = 14; NSteppingNumbers(N); return 0;} |
Java
// Java Program to print first N// Stepping numbersimport java.util.*;public class GFG{ static HashSet<Integer> s = new HashSet<Integer>(); // Function to generate // the Stepping numbers static void generateSteppingNos(int x) { if (x > 1e8) return; // Inserting the current // element in the set s.add(x); // Retrieving the last digit // of the current number int last = x % 10; if (last - 1 >= 0) // Appending x-1 to // the current number generateSteppingNos(x * 10 + last - 1); // Appending x to // the current number generateSteppingNos(x * 10 + last); if (last + 1 <= 9) // Appending x+1 to // the current number generateSteppingNos(x * 10 + last + 1); } // Function to print // N Stepping numbers static void NSteppingNumbers(int N) { HashSet<Integer> s = new HashSet<Integer>(); int[] arr = {10, 11, 12, 21, 22}; for (int i = 1; i <= 9; i++) { generateSteppingNos(i); s.add(i); } for(int i = 0; i < arr.length; i++) { s.add(arr[i]); } int count = 1; // Printing N numbers from s for(int it : s) { if (count <= N) { System.out.print(it + ", "); count++; } else break; } } public static void main(String[] args) { int N = 14; NSteppingNumbers(N); }}// This code is contributed by mukesh07. |
Python3
# Python3 Program to print first N # Stepping numbers # Function to generate # the Stepping numbers def generateSteppingNos(x, s): if (x > 1e8): return # Inserting the current # element in the set s.add(x) # Retrieving the last digit # of the current number last = x % 10 if (last - 1 >= 0): # Appending x-1 to # the current number generateSteppingNos(x * 10 + last - 1, s) # Appending x to # the current number generateSteppingNos(x * 10 + last, s) if (last + 1 <= 9): # Appending x+1 to # the current number generateSteppingNos(x * 10 + last + 1, s)# Function to print # N Stepping numbers def NSteppingNumbers(N): s = set() for i in range(1, 10): generateSteppingNos(i, s) count = 1 s.pop() # Printing N numbers from s for value in s: if (count <= N): print(value, end=', ') count = count + 1 else: break# Driver code N = 14NSteppingNumbers(N)# This code is contributed by Sanjit_Prasad |
C#
// C# Program to print first N// Stepping numbersusing System;using System.Collections.Generic;class GFG { static HashSet<int> s = new HashSet<int>(); // Function to generate // the Stepping numbers static void generateSteppingNos(int x) { if (x > 1e8) return; // Inserting the current // element in the set s.Add(x); // Retrieving the last digit // of the current number int last = x % 10; if (last - 1 >= 0) // Appending x-1 to // the current number generateSteppingNos(x * 10 + last - 1); // Appending x to // the current number generateSteppingNos(x * 10 + last); if (last + 1 <= 9) // Appending x+1 to // the current number generateSteppingNos(x * 10 + last + 1); } // Function to print // N Stepping numbers static void NSteppingNumbers(int N) { HashSet<int> s = new HashSet<int>(); int[] arr = {10, 11, 12, 21, 22}; for (int i = 1; i <= 9; i++) { generateSteppingNos(i); s.Add(i); } for(int i = 0; i < arr.Length; i++) { s.Add(arr[i]); } int count = 1; // Printing N numbers from s foreach(int it in s) { if (count <= N) { Console.Write(it + ", "); count++; } else break; } } static void Main() { int N = 14; NSteppingNumbers(N); }}// This code is contributed by suresh07. |
Javascript
// JavaScript program to print first N Stepping numbers// Set to store the stepping numberslet s = new Set();// Function to generate the stepping numbersfunction generateSteppingNos(x) { if (x > 1e8) { return; } // Inserting the current element in the set s.add(x); // Retrieving the last digit of the current number let last = x % 10; if (last - 1 >= 0) { // Appending x-1 to the current number generateSteppingNos(x * 10 + last - 1); } // Appending x to the current number generateSteppingNos(x * 10 + last); if (last + 1 <= 9) { // Appending x+1 to the current number generateSteppingNos(x * 10 + last + 1); }}// Function to print N stepping numbersfunction NSteppingNumbers(N) { // Set to store the stepping numbers let s = new Set(); let arr = [10, 11, 12, 21, 22]; // Generating stepping numbers for (let i = 1; i <= 9; i++) { generateSteppingNos(i); s.add(i); } for (let i = 0; i < arr.length; i++) { s.add(arr[i]); } let count = 1; // Printing N numbers from the set let ans = []; for (let it of s) { if (count <= N) { ans.push(it); count++; } else { break; } } console.log(ans.join(', '))}let N = 14;NSteppingNumbers(N);// This code is contributed by codebraxnzt |
Output:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22,
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!