Dados dos enteros n y k , encuentre el palíndromo lexicográfico n – ésimo de k dígitos.
Ejemplos:
Input : n = 5, k = 4 Output : 1441 Explanation: 4 digit lexicographical palindromes are: 1001, 1111, 1221, 1331, 1441 5th palindrome = 1441 Input : n = 4, k = 6 Output : 103301
Enfoque ingenuo
Una fuerza bruta consiste en ejecutar un bucle desde el número de dígito k-ésimo más pequeño y verificar si cada número es palíndromo o no. Si es un número palíndromo entonces decrementa el valor de k. Por lo tanto, el bucle se ejecuta hasta que k se agota.
C++
// A naive approach of C++ program of finding nth
// palindrome of k digit
#include<bits/stdc++.h>
using namespace std;
// Utility function to reverse the number n
int reverseNum(int n)
{
int rem, rev=0;
while (n)
{
rem = n % 10;
rev = rev * 10 + rem;
n /= 10;
}
return rev;
}
// Boolean Function to check for palindromic
// number
bool isPalindrom(int num)
{
return num == reverseNum(num);
}
// Function for finding nth palindrome of k digits
int nthPalindrome(int n,int k)
{
// Get the smallest k digit number
int num = (int)pow(10, k-1);
while (true)
{
// check the number is palindrom or not
if (isPalindrom(num))
--n;
// if n'th palindrome found break the loop
if (!n)
break;
// Increment number for checking next palindrome
++num;
}
return num;
}
// Driver code
int main()
{
int n = 6, k = 5;
printf("%dth palindrome of %d digit = %d\n",
n, k, nthPalindrome(n, k));
n = 10, k = 6;
printf("%dth palindrome of %d digit = %d",
n, k, nthPalindrome(n, k));
return 0;
}
Java
// A naive approach of Java program of finding nth
// palindrome of k digit
import java.util.*;
class GFG
{
// Utility function to reverse the number n
static int reverseNum(int n)
{
int rem, rev = 0;
while (n > 0)
{
rem = n % 10;
rev = rev * 10 + rem;
n /= 10;
}
return rev;
}
// Boolean Function to check for palindromic
// number
static boolean isPalindrom(int num)
{
return num == reverseNum(num);
}
// Function for finding nth palindrome of k digits
static int nthPalindrome(int n, int k)
{
// Get the smallest k digit number
int num = (int)Math.pow(10, k-1);
while (true)
{
// check the number is palindrom or not
if (isPalindrom(num))
--n;
// if n'th palindrome found break the loop
if (n == 0)
break;
// Increment number for checking next palindrome
++num;
}
return num;
}
// Driver code
public static void main(String[] args)
{
int n = 6, k = 5;
System.out.println(n + "th palindrome of " + k + " digit = " + nthPalindrome(n, k));
n = 10; k = 6;
System.out.println(n + "th palindrome of " + k + " digit = " + nthPalindrome(n, k));
}
}
// This code is contributed by mits
Python3
# A naive approach of Python3 program # of finding nth palindrome of k digit import math; # Utility function to # reverse the number n def reverseNum(n): rev = 0; while (n): rem = n % 10; rev = (rev * 10) + rem; n = int(n / 10); return rev; # Boolean Function to check for # palindromic number def isPalindrom(num): return num == reverseNum(num); # Function for finding nth # palindrome of k digits def nthPalindrome(n, k): # Get the smallest k digit number num = math.pow(10, k - 1); while (True): # check the number is # palindrom or not if (isPalindrom(num)): n-=1; # if n'th palindrome found # break the loop if (not n): break; # Increment number for checking # next palindrome num+=1; return int(num); # Driver code n = 6; k = 5; print(n,"th palindrome of",k,"digit =",nthPalindrome(n, k)); n = 10; k = 6; print(n,"th palindrome of",k,"digit =",nthPalindrome(n, k)); # This code is contributed by mits
C#
// A naive approach of C# program of finding nth
// palindrome of k digit
using System;
class GFG
{
// Utility function to reverse the number n
static int reverseNum(int n)
{
int rem, rev = 0;
while (n > 0)
{
rem = n % 10;
rev = rev * 10 + rem;
n /= 10;
}
return rev;
}
// Boolean Function to check for palindromic
// number
static bool isPalindrom(int num)
{
return num == reverseNum(num);
}
// Function for finding nth palindrome of k digits
static int nthPalindrome(int n, int k)
{
// Get the smallest k digit number
int num = (int)Math.Pow(10, k-1);
while (true)
{
// check the number is palindrom or not
if (isPalindrom(num))
--n;
// if n'th palindrome found break the loop
if (n == 0)
break;
// Increment number for checking next palindrome
++num;
}
return num;
}
// Driver code
public static void Main()
{
int n = 6, k = 5;
Console.WriteLine(n + "th palindrome of " + k + " digit = " + nthPalindrome(n, k));
n = 10; k = 6;
Console.WriteLine(n + "th palindrome of " + k + " digit = " + nthPalindrome(n, k));
}
}
// This code is contributed
// by Akanksha Rai
PHP
<?php
// A naive approach of PHP program
// of finding nth palindrome of k digit
// Utility function to
// reverse the number n
function reverseNum($n)
{
$rem;
$rev = 0;
while ($n)
{
$rem = $n % 10;
$rev = ($rev * 10) + $rem;
$n = (int)($n / 10);
}
return $rev;
}
// Boolean Function to check for
// palindromic number
function isPalindrom($num)
{
return $num == reverseNum($num);
}
// Function for finding nth
// palindrome of k digits
function nthPalindrome($n, $k)
{
// Get the smallest k digit number
$num = pow(10, $k - 1);
while (true)
{
// check the number is
// palindrom or not
if (isPalindrom($num))
--$n;
// if n'th palindrome found
// break the loop
if (!$n)
break;
// Increment number for checking
// next palindrome
++$num;
}
return $num;
}
// Driver code
$n = 6;
$k = 5;
echo $n, "th palindrome of ", $k, " digit = ",
nthPalindrome($n, $k), "\n";
$n = 10;
$k = 6;
echo $n,"th palindrome of ", $k, " digit = ",
nthPalindrome($n, $k), "\n";
// This code is contributed by ajit
?>
Javascript
<script>
// A naive approach of Javascript
// program of finding nth
// palindrome of k digit
// Utility function to
// reverse the number n
function reverseNum(n)
{
let rem, rev = 0;
while (n > 0)
{
rem = n % 10;
rev = rev * 10 + rem;
n = parseInt(n / 10);
}
return rev;
}
// Boolean Function to
// check for palindromic
// number
function isPalindrom(num)
{
return num == reverseNum(num);
}
// Function for finding nth
// palindrome of k digits
function nthPalindrome(n, k)
{
// Get the smallest k digit number
let num = Math.pow(10, k-1);
while (true)
{
// check the number is
// palindrom or not
if (isPalindrom(num))
--n;
// if n'th palindrome found
// break the loop
if (n == 0)
break;
// Increment number for checking
// next palindrome
++num;
}
return num;
}
let n = 6, k = 5;
document.write(n + "th palindrome of " + k +
" digit = " + nthPalindrome(n, k) + "</br>");
n = 10; k = 6;
document.write(n + "th palindrome of " + k +
" digit = " + nthPalindrome(n, k));
</script>
Producción:
6th palindrome of 5 digit = 10501 10th palindrome of 6 digit = 109901
Complejidad temporal: O(10 k )
Espacio auxiliar: O(1), ya que no se ha ocupado espacio extra.
Enfoque eficiente
Un método eficiente es buscar un patrón. De acuerdo con la propiedad del palíndromo primero, los medios dígitos son los mismos que los demás medios dígitos en orden inverso. Por lo tanto, solo necesitamos buscar los primeros medios dígitos, ya que el resto se puede generar fácilmente. Tomemos k = 8, el palíndromo más pequeño siempre comienza con 1 como dígito principal y sigue así para los primeros 4 dígitos del número.
First half values for k = 8 1st: 1000 2nd: 1001 3rd: 1002 ... ... 100th: 1099 So we can easily write the above sequence for nth palindrome as: (n-1) + 1000 For k digit number, we can generalize above formula as: If k is odd => num = (n-1) + 10k/2 else => num = (n-1) + 10k/2 - 1 Now rest half digits can be expanded by just printing the value of num in reverse order. But before this if k is odd then we have to truncate the last digit of a value num
Ilustración:
n = 6 k = 5
- Determine el número de primeros medios dígitos = piso (5/2) = 2
- Utilice la fórmula: núm = (6-1) + 10 2 = 105
- Expanda los medios dígitos restantes invirtiendo el valor de num.
La respuesta final será 10501
A continuación se muestra la implementación de los pasos anteriores.
C++
// C++ program of finding nth palindrome
// of k digit
#include<bits/stdc++.h>
using namespace std;
void nthPalindrome(int n, int k)
{
// Determine the first half digits
int temp = (k & 1) ? (k / 2) : (k/2 - 1);
int palindrome = (int)pow(10, temp);
palindrome += n - 1;
// Print the first half digits of palindrome
printf("%d", palindrome);
// If k is odd, truncate the last digit
if (k & 1)
palindrome /= 10;
// print the last half digits of palindrome
while (palindrome)
{
printf("%d", palindrome % 10);
palindrome /= 10;
}
printf("\n");
}
// Driver code
int main()
{
int n = 6, k = 5;
printf("%dth palindrome of %d digit = ",n ,k);
nthPalindrome(n ,k);
n = 10, k = 6;
printf("%dth palindrome of %d digit = ",n ,k);
nthPalindrome(n, k);
return 0;
}
Java
// Java program of finding nth palindrome
// of k digit
class GFG{
static void nthPalindrome(int n, int k)
{
// Determine the first half digits
int temp = (k & 1)!=0 ? (k / 2) : (k/2 - 1);
int palindrome = (int)Math.pow(10, temp);
palindrome += n - 1;
// Print the first half digits of palindrome
System.out.print(palindrome);
// If k is odd, truncate the last digit
if ((k & 1)>0)
palindrome /= 10;
// print the last half digits of palindrome
while (palindrome>0)
{
System.out.print(palindrome % 10);
palindrome /= 10;
}
System.out.println("");
}
// Driver code
public static void main(String[] args)
{
int n = 6, k = 5;
System.out.print(n+"th palindrome of "+k+" digit = ");
nthPalindrome(n ,k);
n = 10;
k = 6;
System.out.print(n+"th palindrome of "+k+" digit = ");
nthPalindrome(n, k);
}
}
// This code is contributed by mits
Python3
# Python3 program of finding nth palindrome # of k digit def nthPalindrome(n, k): # Determine the first half digits if(k & 1): temp = k // 2 else: temp = k // 2 - 1 palindrome = 10**temp palindrome = palindrome + n - 1 # Print the first half digits of palindrome print(palindrome, end="") # If k is odd, truncate the last digit if(k & 1): palindrome = palindrome // 10 # print the last half digits of palindrome while(palindrome): print(palindrome % 10, end="") palindrome = palindrome // 10 # Driver code if __name__=='__main__': n = 6 k = 5 print(n, "th palindrome of", k, " digit = ", end=" ") nthPalindrome(n, k) print() n = 10 k = 6 print(n, "th palindrome of", k, "digit = ",end=" ") nthPalindrome(n, k) # This code is contributed by # Sanjit_Prasad
C#
// C# program of finding nth palindrome
// of k digit
using System;
class GFG
{
static void nthPalindrome(int n, int k)
{
// Determine the first half digits
int temp = (k & 1) != 0 ? (k / 2) : (k / 2 - 1);
int palindrome = (int)Math.Pow(10, temp);
palindrome += n - 1;
// Print the first half digits
// of palindrome
Console.Write(palindrome);
// If k is odd, truncate the last digit
if ((k & 1) > 0)
palindrome /= 10;
// print the last half digits
// of palindrome
while (palindrome>0)
{
Console.Write(palindrome % 10);
palindrome /= 10;
}
Console.WriteLine("");
}
// Driver code
static public void Main ()
{
int n = 6, k = 5;
Console.Write(n+"th palindrome of " + k +
" digit = ");
nthPalindrome(n, k);
n = 10;
k = 6;
Console.Write(n+"th palindrome of " + k +
" digit = ");
nthPalindrome(n, k);
}
}
// This code is contributed by ajit
PHP
<?php
// PHP program of finding nth palindrome
// of k digit
function nthPalindrome($n, $k)
{
// Determine the first half digits
$temp = ($k & 1) ?
(int)($k / 2) : (int)($k / 2 - 1);
$palindrome = (int)pow(10, $temp);
$palindrome += $n - 1;
// Print the first half digits of palindrome
print($palindrome);
// If k is odd, truncate the last digit
if ($k & 1)
$palindrome = (int)($palindrome / 10);
// print the last half digits of palindrome
while ($palindrome > 0)
{
print($palindrome % 10);
$palindrome = (int)($palindrome / 10);
}
print("\n");
}
// Driver code
$n = 6;
$k = 5;
print($n."th palindrome of $k digit = ");
nthPalindrome($n, $k);
$n = 10;
$k = 6;
print($n."th palindrome of $k digit = ");
nthPalindrome($n, $k);
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program of finding nth palindrome of k digit
function nthPalindrome(n, k)
{
// Determine the first half digits
let temp = (k & 1) != 0 ? parseInt(k / 2, 10) : (parseInt(k / 2, 10) - 1);
let palindrome = parseInt(Math.pow(10, temp), 10);
palindrome += n - 1;
// Print the first half digits
// of palindrome
document.write(palindrome);
// If k is odd, truncate the last digit
if ((k & 1) > 0)
palindrome = parseInt(palindrome / 10, 10);
// print the last half digits
// of palindrome
while (palindrome>0)
{
document.write(palindrome % 10);
palindrome = parseInt(palindrome / 10, 10);
}
document.write("" + "</br>");
}
let n = 6, k = 5;
document.write(n+"th palindrome of " + k + " digit = ");
nthPalindrome(n, k);
n = 10;
k = 6;
document.write(n+"th palindrome of " + k + " digit = ");
nthPalindrome(n, k);
</script>
Producción:
6th palindrome of 5 digit = 10501 10th palindrome of 6 digit = 109901
Complejidad de tiempo: O(k)
Espacio auxiliar: O(1)
Referencia:
http://stackoverflow.com/questions/11925840/how-to-calculate-nth-n-digit-palindrome-ficiently
Este artículo es una contribución de Shubham Bansal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA