Print Nth Stepping or Autobiographical number
Given a natural number N, the task is to print the Nth Stepping or Autobiographical number.
A number is called stepping number if all adjacent digits have an absolute difference of 1. The following series is a list of Stepping natural numbers:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23, 32, ….
Examples:
Input: N = 16 Output: 32 Explanation: 16th Stepping number is 32. Input: N = 14 Output: 22 Explanation: 14th Stepping number is 22.
Approach: This problem can be solved using Queue data structure. First, prepare an empty queue, and Enqueue 1, 2, …, 9 in this order.
Then inorder the generate the Nth Stepping number, the following operations has to be performed N times:
- Perform Dequeue from the Queue. Let x be the dequeued element.
- If x mod 10 is not equal to 0, then Enqueue 10x + (x mod 10) – 1
- Enqueue 10x + (x mod 10).
- If x mod 10 is not equal to 9, then Enqueue 10x + (x mod 10) + 1.
The dequeued number in the N-th operation is the N-th Stepping Number.
Below is the implementation of the above approach:
C++
// C++ implementation to find // N’th stepping natural Number #include <bits/stdc++.h> using namespace std; // Function to find the // Nth stepping natural number int NthSmallest( int K) { // Declare the queue queue< int > Q; int x; // Enqueue 1, 2, ..., 9 in this order for ( int i = 1; i < 10; i++) Q.push(i); // Perform K operation on queue for ( int i = 1; i <= K; i++) { // Get the ith Stepping number x = Q.front(); // Perform Dequeue from the Queue Q.pop(); // If x mod 10 is not equal to 0 if (x % 10 != 0) { // then Enqueue 10x + (x mod 10) - 1 Q.push(x * 10 + x % 10 - 1); } // Enqueue 10x + (x mod 10) Q.push(x * 10 + x % 10); // If x mod 10 is not equal to 9 if (x % 10 != 9) { // then Enqueue 10x + (x mod 10) + 1 Q.push(x * 10 + x % 10 + 1); } } // Return the dequeued number of the K-th // operation as the Nth stepping number return x; } // Driver Code int main() { // initialise K int N = 16; cout << NthSmallest(N) << "\n" ; return 0; } |
Java
// Java implementation to find // N'th stepping natural Number import java.util.*; class GFG{ // Function to find the // Nth stepping natural number static int NthSmallest( int K) { // Declare the queue Queue<Integer> Q = new LinkedList<>(); int x = 0 ; // Enqueue 1, 2, ..., 9 in this order for ( int i = 1 ; i < 10 ; i++) Q.add(i); // Perform K operation on queue for ( int i = 1 ; i <= K; i++) { // Get the ith Stepping number x = Q.peek(); // Perform Dequeue from the Queue Q.remove(); // If x mod 10 is not equal to 0 if (x % 10 != 0 ) { // then Enqueue 10x + (x mod 10) - 1 Q.add(x * 10 + x % 10 - 1 ); } // Enqueue 10x + (x mod 10) Q.add(x * 10 + x % 10 ); // If x mod 10 is not equal to 9 if (x % 10 != 9 ) { // then Enqueue 10x + (x mod 10) + 1 Q.add(x * 10 + x % 10 + 1 ); } } // Return the dequeued number of the K-th // operation as the Nth stepping number return x; } // Driver Code public static void main(String[] args) { // initialise K int N = 16 ; System.out.print(NthSmallest(N)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to find # N’th stepping natural Number # Function to find the # Nth stepping natural number def NthSmallest(K): # Declare the queue Q = [] # Enqueue 1, 2, ..., 9 in this order for i in range ( 1 , 10 ): Q.append(i) # Perform K operation on queue for i in range ( 1 ,K + 1 ): # Get the ith Stepping number x = Q[ 0 ] # Perform Dequeue from the Queue Q.remove(Q[ 0 ]) # If x mod 10 is not equal to 0 if (x % 10 ! = 0 ): # then Enqueue 10x + (x mod 10) - 1 Q.append(x * 10 + x % 10 - 1 ) # Enqueue 10x + (x mod 10) Q.append(x * 10 + x % 10 ) # If x mod 10 is not equal to 9 if (x % 10 ! = 9 ): # then Enqueue 10x + (x mod 10) + 1 Q.append(x * 10 + x % 10 + 1 ) # Return the dequeued number of the K-th # operation as the Nth stepping number return x # Driver Code if __name__ = = '__main__' : # initialise K N = 16 print (NthSmallest(N)) # This code is contributed by Surendra_Gangwar |
C#
// C# implementation to find // N'th stepping natural Number using System; using System.Collections.Generic; class GFG{ // Function to find the // Nth stepping natural number static int NthSmallest( int K) { // Declare the queue List< int > Q = new List< int >(); int x = 0; // Enqueue 1, 2, ..., 9 in this order for ( int i = 1; i < 10; i++) Q.Add(i); // Perform K operation on queue for ( int i = 1; i <= K; i++) { // Get the ith Stepping number x = Q[0]; // Perform Dequeue from the Queue Q.RemoveAt(0); // If x mod 10 is not equal to 0 if (x % 10 != 0) { // then Enqueue 10x + (x mod 10) - 1 Q.Add(x * 10 + x % 10 - 1); } // Enqueue 10x + (x mod 10) Q.Add(x * 10 + x % 10); // If x mod 10 is not equal to 9 if (x % 10 != 9) { // then Enqueue 10x + (x mod 10) + 1 Q.Add(x * 10 + x % 10 + 1); } } // Return the dequeued number of the K-th // operation as the Nth stepping number return x; } // Driver Code public static void Main(String[] args) { // initialise K int N = 16; Console.Write(NthSmallest(N)); } } // This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript implementation to find // N’th stepping natural Number // Function to find the // Nth stepping natural number function NthSmallest(K) { // Declare the queue var Q = []; var x; // Enqueue 1, 2, ..., 9 in this order for ( var i = 1; i < 10; i++) Q.push(i); // Perform K operation on queue for ( var i = 1; i <= K; i++) { // Get the ith Stepping number x = Q[0]; // Perform Dequeue from the Queue Q.shift(); // If x mod 10 is not equal to 0 if (x % 10 != 0) { // then Enqueue 10x + (x mod 10) - 1 Q.push(x * 10 + x % 10 - 1); } // Enqueue 10x + (x mod 10) Q.push(x * 10 + x % 10); // If x mod 10 is not equal to 9 if (x % 10 != 9) { // then Enqueue 10x + (x mod 10) + 1 Q.push(x * 10 + x % 10 + 1); } } // Return the dequeued number of the K-th // operation as the Nth stepping number return x; } // Driver Code // initialise K var N = 16; document.write( NthSmallest(N)); // This code is contributed by famously. </script> |
Output:
32
Time Complexity: O(N)
Auxiliary Space: O(N)