Encuentra los primeros N números puros

Dado un número entero N , la tarea es imprimir los primeros N ^números puros. Se dice que un número es puro si

1. Tiene un número par de dígitos.
2. Todos los dígitos son 4 o 5 .
3. Y el número es un palíndromo.

Los primeros números puros son 44, 55, 4444, 4554, 5445, 5555, …

Ejemplos:

Entrada: N = 4
Salida: 44 55 4444 5445

Entrada: N = 10
Salida: 44 55 4444 4554 5445 5555 444444 454454 544445 554455

Enfoque: La idea es similar al enfoque discutido aquí . En cada paso de la cola podemos generar el siguiente número sumando 4 y 5 en ambos lados, es decir, el final y el comienzo del número anterior:

q.push("4" + temp + "4");
q.push("5" + temp + "5");

Procediendo de esta manera podemos cuidar palíndromos e incluso números de longitud.

A continuación se muestra la implementación del enfoque anterior:

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
  
// Function to print the first n pure numbers
void nPureNumbers(int n)
{
  
    queue<string> q;
    vector<string> ans;
  
    // Push the starting two elements
    q.push("44");
    q.push("55");
    int total = 2;
  
    // While generated numbers are less than n
    while (ans.size() < n) {
  
        string temp = q.front();
        q.pop();
        ans.push_back(temp);
  
        q.push("4" + temp + "4");
        q.push("5" + temp + "5");
    }
  
    // Sorting strings based on their value
    sort(ans.begin(), ans.end(), [](auto s, auto s2) {
        if (s.size() == s2.size())
            return s < s2;
        else
            return s.size() < s2.size();
    });
  
    // Print first n pure numbers
    for (auto i : ans) {
        cout << i << " ";
    }
}
  
// Driver code
int main()
{
    int n = 4;
  
    nPureNumbers(n);
  
    return 0;
}

44 55 4444 5445

Enfoque 2: El enfoque divide el número palindrómico par en dos partes iguales, las cuales se reflejan entre sí. La idea es construir la primera parte usando el mismo enfoque que se usa para construir un contador binario cambiando cada segundo bit; excepto que, en lugar de voltear 0 y 1, estamos volteando 4 y 5. Luego, usamos la primera parte del número y la propiedad palindrómica para crear el número puro final.

44, 55, 4444, 4554... can be separated out into 
 4 | 4
 5 | 5
44 | 44
45 | 54
54 | 45
55 | 55

Los números imitan la propiedad de los números binarios de los primeros ‘k’ bits donde k = 1, 2, 3 y así sucesivamente.

 0
 1
00
01
10
11

Entonces, comenzamos volteando el último bit después de cada iteración, luego pasamos al bit (k-1) que se voltea después de cada 2 iteraciones y así sucesivamente. La primera vez, se volteará n veces y la siguiente, se volteará n/2 veces y así sucesivamente.

Como n es una suma de todos los números posibles con k bits donde k= 1, 2, 3…, nuestro número será una suma de 2 + 4 + 8 +…2 ^k números. Dividimos consecutivamente n entre 2 y nos detenemos si su valor es igual a cero, ya que no será necesario agregar más bits y también porque, en la próxima iteración, el número se invertirá después del doble de la cantidad de elementos que tomó en el iteración anterior.

Podemos usar una pila para almacenar los valores y luego sacarlos en orden secuencial, o almacenar los datos en una string y simplemente invertirlos, lo que usa menos espacio que una pila.

#include <bits/stdc++.h>
using namespace std;
  
// Creating a function 'pure' that returns the pure number 
// in the form of a string.
string pure(int n)
{
    // initializing string p where the number will be stored
    string p; 
  
    // It keeps on adding numbers as long as n>0
    while (n > 0) { 
  
        // To equalize the value of n to the corresponding flips 
        n--; 
        if (n % 2 == 0)
            p.append("4");
        else
            p.append("5");
  
        // Dividing n by 2 to move to the next bit
        n /= 2; 
    }
  
    int len = p.length(); // Taking the length of the string
    reverse(p.begin(), p.end()); // Reversing the string
  
    for (int i = len - 1; i >= 0; i--) // Building the palindrome
        p += p[i];
  
    return p;
}
  
int main()
{
    for (int i = 1; i <= 10; i++)
        cout << pure(i) << " "; // Print Ith pure number
  
    return 0;
}

44 55 4444 4554 5445 5555 444444 445544 454454 455554