Imprimir Número Nth Stepping o Autobiográfico

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)
 

Publicación traducida automáticamente

Artículo escrito por souradeep y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *