Cómo contar el número de enteros palindrómicos dentro de un rango [A, B] donde A y B pueden ser de hasta 10 ^ 17 La tecnología cambia la vida futura

Gracias por el A2A.

Bueno, por lo que parece, básicamente esta pregunta se trata de generar el siguiente número primo más pequeño para un número dado, que es un problema clásico.

La forma en que lo resolvería es así:

Digamos que el rango dado a usted es [num1, num2].

Ahora escriba un método que genere el siguiente número primo más pequeño para num1 y verifique si es menor que num2. En caso afirmativo, aumente su contador y llame de forma recursiva al mismo método esta vez con el rango
[nuevo número de palíndromo, num2]
De esta manera, agota el número de palíndromos y cuenta hasta num2. Cuando el palíndromo finalmente excede el número 2, puede salir.

Algo como esto:

  private static void palin_range (String num1, String num2, int c) {
         if (mayor (num1, num2)) {
             System.out.println (c);
         }
         más{
             Cadena k = genNextPalin (num1);
             if (mayor (num2, k)) {
                 c = c + 1;
                 palin_range (k, num2, c);
             }
             más{
                 System.out.println (c);
             }
            
         }
     }

Observe cómo uso String en lugar de int debido al gran tamaño del número.
Ahora utilizo el método mayor en lugar de comparar directamente porque se tratará de enteros de la magnitud de 10 ^ 17. Tienes que usar BigInteger para comparar los 2 números y debería ser un método fácil. Lo escribiré para ti también.

  privado booleano estático mayor (String num1, String num2) {
     BigInteger n1 = nuevo BigInteger (num1);
     BigInteger n2 = nuevo BigInteger (num2);
     int res = n1.compareTo (n2);
     si (res == 1)
         volver verdadero;
     más
         falso retorno;
 }

Ahora la parte restante es el método genNextPalin () que acepta un número entero y genera el siguiente palíndromo más pequeño. Es un problema clásico y existen muchas explicaciones e implementaciones del mismo. Una simple búsqueda en Google te dará los resultados. Observe qué tan conveniente es el rango hasta 10 ^ 17 y int maneja hasta 10 ^ 9.

Eso debería darte una idea de que atravesar todos los números y verificar palíndromo uno tras otro no es tu mejor opción. Divide el gran número en dos mitades e intenta reflejar la imagen en la siguiente mitad. Debido a esta razón, el rango es 10 ^ 17 cuya imagen reflejada en la mitad izquierda sería 10 ^ 8 que int puede manejar.
Algo como esto:

1. 1234567887654322
2. 12345678 87654322
3. 12345678 87654322
^ ^ igual
3. 12345678 87654322
^ ^ igual
3. 12345678 87654322
^ ^ igual
3. 12345678 87654322
^ ^ igual
3. 12345678 87654322
^ ^ igual
3. 12345678 87654322
^ ^ igual
3. 12345678 87654322
^ ^ igual
3. 12345678 87654322
^ ^ mayor que, así que incremente la izquierda

3. 12345679

4. 1234567997654321 respuesta

Aquí hay un enlace a la pregunta de stackoverflow que explica esta idea: un mejor algoritmo para encontrar el próximo palíndromo de una cadena numérica

La implementación del método genNextPalin según stackoverflow se detalla a continuación:

 Cadena estática pública genNextPalin (String base) {// comprueba si es 1 dígito if (base.length () == 1) {if (Integer.parseInt (base) == 9) return "11";  else return (Integer.parseInt (base) +1) + "";  } verificación booleana = verdadero;  // verifica si es todo 9s para (char a: base.toCharArray ()) {if (a! = '9') check = false;  } if (marcar) {String num = "1";  para (int i = 0; i <base.length () - 1; i ++) num + = "0";  num + = "1";  retorno num;  } booleano isBasePalin = isPalindrome (base);  int mid = base.length () / 2;  if (isBasePalin) {// si base es pálido y es extraño, aumente a la mitad y devuelva if (base.length ()% 2 == 1) {BigInteger leftHalf = new BigInteger (base.substring (0, mid + 1)) ;  Cadena newLeftHalf = leftHalf.add (BigInteger.ONE) .toString ();  Cadena newPalin = genPalin2 (newLeftHalf.substring (0, mid), newLeftHalf.charAt (mid));  volver nuevoPalin;  } else {BigInteger leftHalf = new BigInteger (base.substring (0, mid));  Cadena newLeftHalf = leftHalf.add (BigInteger.ONE) .toString ();  Cadena newPalin = genPalin (newLeftHalf.substring (0, mid));  volver nuevoPalin;  }} else {if (base.length ()% 2 == 1) {BigInteger leftHalf = new BigInteger (base.substring (0, mid));  BigInteger rightHalf = new BigInteger (reverse (base.substring (mid + 1, base.length ())));  // verifica si leftHalf es mayor que la mitad derecha if (leftHalf.compareTo (rightHalf) == 1) {String newPalin = genPalin2 (base.substring (0, mid), base.charAt (mid));  volver nuevoPalin;  } else {BigInteger leftHalfMid = new BigInteger (base.substring (0, mid + 1));  Cadena newLeftHalfMid = leftHalfMid.add (BigInteger.ONE) .toString ();  Cadena newPalin = genPalin2 (newLeftHalfMid.substring (0, mid), newLeftHalfMid.charAt (mid));  volver nuevoPalin;  }} else {BigInteger leftHalf = new BigInteger (base.substring (0, mid));  BigInteger rightHalf = new BigInteger (reverse (base.substring (mid, base.length ())));  // verifica si leftHalf es mayor que la mitad derecha if (leftHalf.compareTo (rightHalf) == 1) {return genPalin (base.substring (0, mid));  } else {BigInteger leftHalfMid = new BigInteger (base.substring (0, mid));  Cadena newLeftHalfMid = leftHalfMid.add (BigInteger.ONE) .toString ();  return genPalin (newLeftHalfMid);  }}}} Public static String genPalin (String base) {return base + new StringBuffer (base) .reverse (). toString ();  } Cadena estática pública genPalin2 (String base, char middle) {return base + middle + new StringBuffer (base) .reverse (). toString ();  } Public static String reverse (String in) {return new StringBuffer (in) .reverse (). toString ();  } booleano estático isPalindrome (String str) {int n = str.length ();  for (int i = 0; i <n / 2; i ++) if (str.charAt (i)! = str.charAt (ni-1)) devuelve falso;  volver verdadero;  }

Algoritmos