Dado un entero positivo N , la tarea es encontrar el número palindrómico más grande menor que N y se puede expresar como el producto de dos números de 3 dígitos.
Ejemplos:
Entrada: N = 101110
Salida: 101101
Explicación: El número 101101 ( = 143 * 707) es el número palindrómico más grande posible que satisface las condiciones.Entrada: N = 800000
Salida: 793397
Explicación: El número 793397 ( = 869 × 913) es el número palindrómico más grande posible que satisface las condiciones.
Enfoque ingenuo: el más simple genera todos los pares posibles del rango [100, 999] y para cada par, verifica si su producto es un palíndromo o no y si es menor que N o no. Escriba el máximo de todos los productos obtenidos como respuesta requerida.
Complejidad de Tiempo: O(N * 900 2 )
Espacio Auxiliar: O(1)
Enfoque alternativo: el problema también se puede resolver basándose en la observación de que todos los múltiplos de 11 son palíndromos. Por lo tanto, itere sobre el rango [100, 999] y para cada valor en el rango, itere sobre los múltiplos de 11 en el rango [121, 999] y verifique la condición requerida en cada iteración. Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos num , para almacenar el número palindrómico más grande que satisfaga las condiciones dadas.
- Itere sobre el rango [100, 999] usando una variable, digamos i , y realice los siguientes pasos:
- Iterar sobre el rango [121, 999] usando una variable, digamos j en múltiplos de 11 .
- Almacene el producto de i y j en la string x .
- Si el valor de X es menor que N y X es un palíndromo , actualice el valor de num si X > num .
- De lo contrario, siga iterando para el siguiente par de enteros.
- Iterar sobre el rango [121, 999] usando una variable, digamos j en múltiplos de 11 .
- Después de los pasos anteriores, imprima el valor de num .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the largest palindrome
// not exceeding N which can be expressed
// as the product of two 3-digit numbers
void palindrome_prod(string N){
// Stores all palindromes
vector<int> palindrome_list;
for (int i = 101; i < 1000; i++)
{
for (int j = 121; j < 1000;
j += (i % 11 == 0) ? 1 : 11)
{
// Stores the product
int n = i * j;
string x = to_string(n);
string y = x;
reverse(y.begin(), y.end());
// Check if X is palindrome
if (x == y){
// Check n is less than N
if (n < stoi(N)){
// If true, append it
// in the list
palindrome_list.push_back(i * j);
}
}
}
}
// Print the largest palindrome
cout << (*max_element(palindrome_list.begin(),
palindrome_list.end()));
}
// Driver Code
int main()
{
string N = "101110";
// Function Call
palindrome_prod(N);
return 0;
}
// This code is contributed by mohit kumar 29
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to find the largest palindrome
// not exceeding N which can be expressed
// as the product of two 3-digit numbers
static void palindrome_prod(String N){
// Stores all palindromes
Vector<Integer> palindrome_list = new Vector<Integer>();
for (int i = 101; i < 1000; i++)
{
for (int j = 121; j < 1000;
j += (i % 11 == 0) ? 1 : 11)
{
// Stores the product
int n = i * j;
String x = String.valueOf(n);
String y = x;
reverse(y);
// Check if X is palindrome
if (x == y){
// Check n is less than N
if (n < Integer.valueOf(N)){
// If true, append it
// in the list
palindrome_list.add(i * j);
}
}
}
}
// Print the largest palindrome
System.out.print(Collections.max(palindrome_list));
}
static String reverse(String input)
{
char[] a = input.toCharArray();
int l, r = a.length - 1;
for (l = 0; l < r; l++, r--)
{
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.valueOf(a);
}
// Driver Code
public static void main(String[] args)
{
String N = "101110";
// Function Call
palindrome_prod(N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach # Function to find the largest palindrome # not exceeding N which can be expressed # as the product of two 3-digit numbers def palindrome_prod(N): # Stores all palindromes palindrome_list = [] for i in range(101, 1000): for j in range(121, 1000, (1 if i % 11 == 0 else 11)): # Stores the product n = i * j x = str(n) # Check if X is palindrome if x == x[::-1]: # Check n is less than N if n < N: # If true, append it # in the list palindrome_list.append(i * j) # Print the largest palindrome print(max(palindrome_list)) # Driver Code N = 101110 # Function Call palindrome_prod(N)
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
// Function to find the largest palindrome
// not exceeding N which can be expressed
// as the product of two 3-digit numbers
static void palindrome_prod(String N){
// Stores all palindromes
List<int> palindrome_list = new List<int>();
for (int i = 101; i < 1000; i++)
{
for (int j = 121; j < 1000;
j += (i % 11 == 0) ? 1 : 11)
{
// Stores the product
int n = i * j;
String x = String.Join("", n);
String y = x;
reverse(y);
// Check if X is palindrome
if (x == y)
{
// Check n is less than N
if (n < Int32.Parse(N))
{
// If true, append it
// in the list
palindrome_list.Add(i * j);
}
}
}
}
// Print the largest palindrome
Console.Write(palindrome_list.Max());
}
static String reverse(String input)
{
char[] a = input.ToCharArray();
int l, r = a.Length - 1;
for (l = 0; l < r; l++, r--)
{
char temp = a[l];
a[l] = a[r];
a[r] = temp;
}
return String.Join("", a);
}
// Driver Code
public static void Main(String[] args)
{
String N = "101110";
// Function Call
palindrome_prod(N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program for the above approach
// Function to find the largest palindrome
// not exceeding N which can be expressed
// as the product of two 3-digit numbers
function palindrome_prod(N){
// Stores all palindromes
var palindrome_list = [];
var i,j;
for (i = 101; i < 1000; i++)
{
for (j = 121; j < 1000;
j += (i % 11 == 0) ? 1 : 11)
{
// Stores the product
var n = i * j;
var x = n.toString();
var y = x;
y = y.split("").reverse().join("");
// Check if X is palindrome
if (x == y){
// Check n is less than N
if (n < Number(N)){
// If true, append it
// in the list
palindrome_list.push(i * j);
}
}
}
}
// Print the largest palindrome
document.write(Math.max.apply(null, palindrome_list));
}
// Driver Code
var N = "101110";
// Function Call
palindrome_prod(N);
</script>
101101
Complejidad de Tiempo: O(N*900 2 )
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por nischaygowda777 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA