Dado un valor N , encuentre el número palíndromo más grande que es el producto de dos números de N dígitos.
Ejemplos:
Entrada: N = 2
Salida: 9009
Explicación:
9009 es el número más grande que es producto de dos números de 2 dígitos 91 y 99 (9009 = 91*99)
Entrada: N = 3
Salida: 906609
Entrada: N = 4
Salida: 99000099
Observación: Se puede hacer la siguiente observación para el problema anterior:
Sea N = 2, entonces el producto tendrá 4 dígitos. Dado que el producto será un palíndromo, será de la forma » abba «, donde a, b son dígitos en su respectivo valor posicional.
Por lo tanto,
Para N = 2:
“abba” = 1000a + 100b + 10b + a
= 1001a + 110b
= 11.(91a + 10b)
De manera similar, para N = 3:
“abccba” = 100000a + 10000b + 1000c + 100c + 10b + 1a
= 100001a + 10010b + 1100c
= 11. (9091a + 910b + 100c)
para n = 5:
“ABCDeedcba» = 1000000000A + 1000000B + 10000000C+ 1000000D + 100000E + 10000E + 1000D + 100C+ 10B + A
= 1000000001A + 1000000B + 10000100C+ 100100d + 110000e
= 11.(90909091a + 909091b + 91000c + 10000d)
Enfoque: A partir de la observación anterior, se puede observar un patrón de que todo producto palíndromo siempre tendrá un factor 11.
- Para cualquier número de N dígitos P y Q, si el producto de P y Q es un palíndromo, entonces P o Q son divisibles por 11 pero no por ambos.
- Por lo tanto, en lugar de verificar si el producto de P y Q es un palíndromo para todos los pares posibles de P y Q, podemos reducir el número de cálculos verificando solo los múltiplos de 11 para uno de los números.
A continuación se muestra la implementación del enfoque anterior:
Java
// Java implementation of the above approach
public class GFG {
// Function to check if a number is a
// Palindrome or not
static boolean isPalindrome(long x)
{
// Taking the string value
// of the number
String num = String.valueOf(x);
boolean result = true;
int i = 0;
int j = num.length() - 1;
// Loop to check if every i-th
// character from beginning is
// equal to every (N - i)th char
while (i < j && result) {
result = num.charAt(i++)
== num.charAt(j--);
}
return result;
}
// Function to find the largest palindrome
// which is a product of two N digited numbers
public static void find(final int nDigits)
{
// Find lowerBound, upperBound for
// a given nDigits. for n=2; [10, 99]
final long lowerBound
= (long)Math.pow(10, nDigits - 1);
final long upperBound
= (lowerBound * 10) - 1;
// Result variables
long resultP = 0, resultQ = 0,
resultR = 0;
// Keep p decrementing by 11
for (long p = upperBound;
p > lowerBound;
p -= 11) {
// Find the nearest number
// divisible by 11
while (p % 11 != 0) {
p--;
}
// Keep decrementing q by 1
for (long q = upperBound;
q > lowerBound;
q--) {
long t = p * q;
// Update the result if
// t > r and is a palindrome
if (t > resultR
&& isPalindrome(t)) {
resultP = p;
resultQ = q;
resultR = t;
break;
}
}
}
// Printing the final result
System.out.println(resultR);
}
// Driver code
public static void main(String[] args)
{
int N = 2;
find(N);
}
}
Python3
# Python 3 implementation of # the above approach # Function to check if a # number is a Palindrome # or not def isPalindrome(x): # Taking the string value # of the number num = str(x) result = True i = 0 j = len(num) - 1 # Loop to check if every i-th # character from beginning is # equal to every(N - i)th char while (i < j and result): result = num[i] == num[j] i += 1 j -= 1 return result # Function to find the largest # palindrome which is a product # of two N digited numbers def find(nDigits): # Find lowerBound, upperBound # for a given nDigits. for n = 2 # [10, 99] lowerBound = pow(10, nDigits - 1) upperBound = (lowerBound * 10) - 1 # Result variables resultP = 0 resultQ = 0 resultR = 0 # Keep p decrementing by 11 for p in range(upperBound, lowerBound, -11): # Find the nearest number # divisible by 11 while (p % 11 != 0): p -= 1 # Keep decrementing q by 1 for q in range(upperBound, lowerBound, -1): t = p * q # Update the result if # t > r and is a palindrome if (t > resultR and isPalindrome(t)): resultP = p resultQ = q resultR = t break # Printing the final result print(resultR) # Driver code if __name__ == "__main__": N = 2 find(N) # This code is contributed by Chitranayal
C#
// C# implementation of the above approach
using System;
class GFG {
// Function to check if a number is a
// Palindrome or not
static bool isPalindrome(long x)
{
// Taking the string value
// of the number
String num = String.Join("",x);
bool result = true;
int i = 0;
int j = num.Length - 1;
// Loop to check if every i-th
// character from beginning is
// equal to every (N - i)th char
while (i < j && result) {
result = num[i++]
== num[j--];
}
return result;
}
// Function to find the largest palindrome
// which is a product of two N digited numbers
public static void find(int nDigits)
{
// Find lowerBound, upperBound for
// a given nDigits. for n=2; [10, 99]
long lowerBound
= (long)Math.Pow(10, nDigits - 1);
long upperBound
= (lowerBound * 10) - 1;
// Result variables
long resultP = 0, resultQ = 0,
resultR = 0;
// Keep p decrementing by 11
for (long p = upperBound;
p > lowerBound;
p -= 11) {
// Find the nearest number
// divisible by 11
while (p % 11 != 0) {
p--;
}
// Keep decrementing q by 1
for (long q = upperBound;
q > lowerBound;
q--) {
long t = p * q;
// Update the result if
// t > r and is a palindrome
if (t > resultR
&& isPalindrome(t)) {
resultP = p;
resultQ = q;
resultR = t;
break;
}
}
}
// Printing the readonly result
Console.WriteLine(resultR);
}
// Driver code
public static void Main(String[] args)
{
int N = 2;
find(N);
}
}
// This code is contributed by sapnasingh4991
Javascript
<script>
// Javascript implementation of the above approach
// Function to check if a number is a
// Palindrome or not
function isPalindrome(x)
{
// Taking the string value
// of the number
let num = x.toString();
let result = true;
let i = 0;
let j = num.length - 1;
// Loop to check if every i-th
// character from beginning is
// equal to every (N - i)th char
while (i < j && result) {
result = num[i++]
== num[j--];
}
return result;
}
// Function to find the largest palindrome
// which is a product of two N digited numbers
function find(nDigits)
{
// Find lowerBound, upperBound for
// a given nDigits. for n=2; [10, 99]
let lowerBound
= Math.floor(Math.pow(10, nDigits - 1));
let upperBound
= (lowerBound * 10) - 1;
// Result variables
let resultP = 0, resultQ = 0,
resultR = 0;
// Keep p decrementing by 11
for (let p = upperBound;
p > lowerBound;
p -= 11) {
// Find the nearest number
// divisible by 11
while (p % 11 != 0) {
p--;
}
// Keep decrementing q by 1
for (let q = upperBound;
q > lowerBound;
q--) {
let t = p * q;
// Update the result if
// t > r and is a palindrome
if (t > resultR
&& isPalindrome(t)) {
resultP = p;
resultQ = q;
resultR = t;
break;
}
}
}
// Printing the readonly result
document.write(resultR);
}
// Driver Code
let N = 2;
find(N);
</script>
9009
Complejidad de tiempo: O (límite superior – límite inferior) 2
Espacio Auxiliar: O(1)
Artículo Relacionado: Palíndromo más grande que es producto de dos números de n dígitos
Publicación traducida automáticamente
Artículo escrito por Yajna_Pandith y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA