Encuentre el K-ésimo número palíndromo de longitud impar más pequeño

Dado un entero positivo K , la tarea es encontrar la longitud impar del número palindrómico K ^-ésimo más pequeño .

Ejemplos:

Entrada: K = 5
Salida: 5
Explicación:
Los números palindrómicos de longitudes impares son {1, 2, 3, 4, 5, 6, 7, …, }. El quinto ^{número palindrómico} más pequeño es 5.

Entrada: K = 10
Salida: 101

Enfoque: El problema dado se puede resolver con base en las siguientes observaciones:

• Los primeros números palindrómicos de longitud 1 son 1, 2, 3, 4, 5, 6, 7, 8 y 9.
• El primer número palindrómico de longitud 3 es 101, que es el décimo número palíndromo de longitud impar más pequeño. Del mismo modo, 11 , 12 ^, 13 ^, …, 99, ^{los números palindrómicos} más pequeños son 111, 121, 131…, 999 respectivamente.
• Por lo tanto, el número palíndromo de longitud impar ^Kth más pequeño se puede formar uniendo K y el reverso de K excepto el último dígito.

A partir de las observaciones anteriores, el K-ésimo número palindrómico de longitud impar más pequeño se obtiene agregando el reverso de todos los dígitos de K excepto el último al final de K.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the Kth smallest
// odd length palindrome
int oddLengthPalindrome(int k)
{
     
    // Store the original number K
    int palin = k;
 
    // Removing the last digit of K
    k = k / 10;
 
    // Generate the palindrome by
    // appending the reverse of K
    // except last digit to itself
    while (k > 0)
    {
         
        // Find the remainder
        int rev = k % 10;
 
        // Add the digit to palin
        palin = (palin * 10) + rev;
 
        // Divide K by 10
        k = k / 10;
    }
 
    // Return the resultant palindromic
    // number formed
    return palin;
}
 
// Driver Code
int main()
{
    int k = 504;
 
    cout << oddLengthPalindrome(k);
}
 
// This code is contributed by rishavmahato348

// Java program for the above approach
import java.util.*;
import java.lang.*;
 
class GFG{
     
// Function to find the Kth smallest
// odd length palindrome
static int oddLengthPalindrome(int k)
{
     
    // Store the original number K
    int palin = k;
     
    // Removing the last digit of K
    k = k / 10;
     
    // Generate the palindrome by
    // appending the reverse of K
    // except last digit to itself
    while (k > 0)
    { 
         
        // Find the remainder
        int rev = k % 10;
         
        // Add the digit to palin
        palin = (palin * 10) + rev;
         
        // Divide K by 10
        k = k / 10;
    }
     
    // Return the resultant palindromic
    // number formed
    return palin;
}
 
// Driver Code
public static void main(String[] args)
{
    int k = 504;
     
    System.out.println(oddLengthPalindrome(k));
}
}
 
// This code is contributed by Sudhanshu Bhagat & Govind Choudhary

# Python3 program for the above approach
 
# Function to find the Kth smallest
# odd length palindrome number
def oddLengthPalindrome(K):
 
    # Store the original number K
    palin = K
 
    # Removing the last digit of K
    K = K // 10
 
    # Generate the palindrome by
    # appending the reverse of K
    # except last digit to itself
    while (K > 0):
       
        # Find the remainder
        rev = K % 10
         
        # Add the digit to palin
        palin = palin * 10 + rev
         
        # Divide K by 10
        K = K // 10
 
    # Return the resultant palindromic
    # number formed
    return palin
 
# Driver Code
if __name__ == '__main__':
 
    K = 504
    print(oddLengthPalindrome(K))
     
     
#Contributed by Govind Choudhary & Pallav Pushparaj

// C# program for the above approach
using System;
 
class GFG{
     
// Function to find the Kth smallest
// palindrome of odd length
static int oddLengthPalindrome(int k)
{
     
    // Store the original number K
    int palin = k;
     
    // Removing the last digit of K
    k = k / 10;
     
    // Generate the palindrome by
    // appending the reverse of K
    // except last digit to itself
    while (k > 0)
    {
         
        // Find the remainder
        int rev = k % 10;
         
        // Add the digit to palin
        palin = (palin * 10) + rev;
         
        // Divide K by 10
        k = k / 10;
    }
     
    // Return the resultant palindromic
    // number formed
    return palin;
}
 
// Driver Code
static void Main(string[] args)
{
    int k = 504;
 
    Console.WriteLine(oddLengthPalindrome(k));
}
}
 
// This code is contributed by Sudhanshu Bhagat & Govind Choudhary

<script>
 
// JavaScript program for the above approach
 
// Function to find the Kth smallest
// odd length palindrome
function oddLengthPalindrome(k)
{
     
    // Store the original number K
    let palin = k;
     
    // Removing the last digit of K
    k = Math.floor(k / 10);
     
    // Generate the palindrome by
    // appending the reverse of K
    // except last digit to itself
    while (k > 0)
    { 
         
        // Find the remainder
        let rev = k % 10;
         
        // Add the digit to palin
        palin = (palin * 10) + rev;
         
        // Divide K by 10
        k = Math.floor(k / 10);
    }
     
    // Return the resultant palindromic
    // number formed
    return palin;
}
 
// Driver Code
 
    let k = 504;
     
    document.write(oddLengthPalindrome(k));
 
// This code is contributed by sanjoy_62.
</script>

50405

Complejidad de Tiempo: O(log ₁₀ K)
Espacio Auxiliar: O(1)