Programa en C++ para encontrar todos los números menores que n, que son palindrómicos en base 10 y base 2.

Encuentra todos los números menores que n, que son palindrómicos tanto en base 10 como en base 2. Ejemplos:

33 is Palindrome in its decimal representation.
100001(binary equivalent of 33) in Binary is a Palindrome.

313 is Palindrome in its decimal representation.
100111001 (binary equivalent of 313) in Binary is a Palindrome.

Fuerza Bruta: Comprobamos todos los números del 1 al n si su representación decimal es palíndromo o no. Además, si un número es palindrómico en base 10, verificamos su representación binaria. Si ambas representaciones encontramos un palíndromo entonces lo imprimimos. Enfoque eficiente: Partimos de 1 y creamos palíndromos de dígitos pares e impares hasta n y verificamos si su representación binaria es palíndromo o no. Nota: Esto reducirá la cantidad de operaciones, ya que deberíamos verificar solo el palíndromo decimal en lugar de verificar todos los números del 1 al n. Este enfoque utiliza dos métodos: int createPalindrome(int input, int b, bool isOdd):El creador del palíndromo toma un número de entrada y una base b, así como un valor booleano que indica si el palíndromo debe tener un número par o impar de dígitos. Toma el número de entrada, lo invierte y lo agrega al número de entrada. Si el resultado debe tener un número impar de dígitos, corta un dígito de la parte invertida. bool IsPalindrome(int number, int b) Toma el número de entrada y calcula su reverso según base b. Devuelve el resultado si el número es igual a su reverso o no. 

// A C++ program for finding numbers which are
// decimal as well as binary palindrome
#include <iostream>
using namespace std;
 
// A utility to check if  number is palindrome on base b
bool IsPalindrome(int number, int b)
{
    int reversed = 0;
    int k = number;
 
    // calculate reverse of number
    while (k > 0) {
        reversed = b * reversed + k % b;
        k /= b;
    }
 
    // return true/false depending upon number is palindrome or not
    return (number == reversed);
}
 
// A utility for creating palindrome
int createPalindrome(int input, int b, bool isOdd)
{
    int n = input;
    int palin = input;
 
    // checks if number of digits is odd or even
    // if odd then neglect the last digit of input in finding reverse
    // as in case of odd number of digits middle element occur once
    if (isOdd)
        n /= b;
 
    // creates palindrome by just appending reverse of number to itself
    while (n > 0) {
        palin = palin * b + (n % b);
        n /= b;
    }
    return palin;
}
 
// Function to print decimal and binary palindromic number
void findPalindromic(int n)
{
    int number;
    for (int j = 0; j < 2; j++) {
        bool isOdd = (j % 2 == 0);
 
        // Creates palindrome of base 10 upto n
        // j always decides digits of created palindrome
        int i = 1;
        while ((number = createPalindrome(i, 10, isOdd)) < n) {
            // if created palindrome of base 10 is
            // binary palindrome
            if (IsPalindrome(number, 2))
                cout << number << " ";
            i++;
        }
    }
}
 
// Driver Program to test above function
int main()
{
    int n = 1000;
    findPalindromic(n);
    return 0;
}

1 3 5 7 9 313 585 717 33 99

Complejidad de tiempo: O(N*log(N)), ya que estamos usando el ciclo while para recorrer N veces en el peor de los casos e IsPalindrome cuesta O(log(N)) que está anidado dentro del ciclo while. 

Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.

Este artículo es una contribución de Shivam Pradhan (anuj_charm) . 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.