Dado un número natural N , la tarea es imprimir el número Nth Stepping o Autobiográfico .
Un número se llama número escalonado si todos los dígitos adyacentes tienen una diferencia absoluta de 1. La siguiente serie es una lista de números naturales escalonados:
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 21, 22, 23, 32, ….
Ejemplos:
Input: N = 16 Output: 32 Explanation: 16th Stepping number is 32. Input: N = 14 Output: 22 Explanation: 14th Stepping number is 22.
Enfoque: este problema se puede resolver utilizando la estructura de datos de cola . Primero, prepare una cola vacía y ponga en cola 1, 2, …, 9 en este orden .
Luego, para generar el número de Paso N, las siguientes operaciones deben realizarse N veces:
- Ejecute Dequeue desde la cola. Sea x el elemento fuera de la cola.
- Si x mod 10 no es igual a 0, entonces Enqueue 10x + (x mod 10) – 1
- En cola 10x + (x mod 10).
- Si x mod 10 no es igual a 9, entonces Enqueue 10x + (x mod 10) + 1.
El número eliminado de la cola en la N-ésima operación es el N-ésimo Número de pasos.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
32
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)