Número más grande del conjunto de anagramas más largo posible de todos los cuadrados perfectos de longitud K

Dado un entero K tal que existe un conjunto de todos los cuadrados perfectos posibles, cada uno de longitud K. A partir de este conjunto de cuadrados perfectos, forme un conjunto de la mayor longitud posible que tenga aquellos números que son anagramas entre sí . La tarea es imprimir el elemento más grande presente en el conjunto generado de anagramas. 
Nota: Si hay más de un conjunto de longitud máxima, imprima el número más grande entre ellos.
 

El anagrama de una string es otra string que contiene los mismos caracteres, solo el orden de los caracteres es diferente. 
 

Ejemplos: 
 

Entrada: K = 2 
Salida: 81 
Explicación: 
Todos los cuadrados posibles de longitud K = 2 son {16, 25, 36, 49, 64, 81}. 
Los conjuntos de anagramas posibles son [16], [25], [36], [49], [64], [81]. 
Por lo tanto, cada conjunto tiene el mismo tamaño, es decir, 1. 
En este caso, imprima el conjunto que contiene el elemento más grande, que es 81.

Entrada: K = 5 
Salida: 96100

Enfoque ingenuo: el enfoque más simple es almacenar todos los cuadrados perfectos de longitud K posibles y formar conjuntos de anagramas válidos usando recursividad . Luego, encuentre el elemento máximo presente en el conjunto de mayor longitud.

Tiempo Complejidad: O(N 2
Espacio Auxiliar: O(N)
 

Enfoque Eficiente: La idea se basa en la observación de que al ordenar los dígitos de los cuadrados perfectos, la secuencia de números del anagrama se iguala. A continuación se muestran los pasos: 
 

  1. Inicialice un Mapa para almacenar todos los números de anagrama correspondientes a los números cuyos dígitos están ordenados.
  2. Genere todos los cuadrados perfectos de longitud K.
  3. Para cada cuadrado perfecto generado, inserte el número en el Mapa correspondiente al número cuyo dígito está ordenado en orden ascendente.
  4. Atraviese el Mapa e imprima el número más grande del conjunto de longitud máxima.

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

CPP

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the largest set of
// perfect squares which are anagram
// to each other
void printResult(
    map<string, set<long long int> > m)
{
    auto max_itr = m.begin();
 
    long long maxi = -1;
 
    for (auto itr = m.begin();
         itr != m.end(); ++itr) {
 
        long long int siz1
            = (itr->second).size();
 
        // Check if size of maximum set
        // is less than the current set
        if (maxi < siz1) {
 
            // Update maximum set
            maxi = siz1;
            max_itr = itr;
        }
 
        // If lengths are equal
        else if (maxi == siz1) {
 
            // Update maximum set to store
            // the set with maximum element
            if ((*(max_itr->second).rbegin())
                < *(itr->second.rbegin())) {
                maxi = siz1;
                max_itr = itr;
            }
        }
    }
 
    // Stores the max element from the set
    long long int result
        = *(max_itr->second).rbegin();
 
    // Print final Result
    cout << result << endl;
}
 
// Function to find the
// perfect squares which are anagrams
void anagramicSquares(long long int k)
{
    // Stores the sequence
    map<string, set<long long int> > m;
 
    // Initialize start and end
    // of perfect squares
    long long int end;
    if (k % 2 == 0)
        end = k / 2;
    else
        end = ((k + 1) / 2);
 
    long long int start = pow(10, end - 1);
    end = pow(10, end);
 
    // Iterate form start to end
    for (long long int i = start;
         i <= end; i++) {
 
        long long int x = i * i;
 
        // Converting int to string
        ostringstream str1;
        str1 << x;
 
        string str = str1.str();
        if (str.length() == k) {
 
            // Sort string for storing
            // number at exact map position
            sort(str.begin(), str.end());
 
            // Insert number at map
            m[str].insert(x);
        }
    }
 
    // Print result
    printResult(m);
}
 
// Driver Code
int main()
{
    // Given K
    long long int K = 2;
 
    // Function Call
    anagramicSquares(K);
 
    return 0;
}
Producción: 

81

 

Complejidad temporal: O(N) 
Espacio auxiliar: O(N)
 

Publicación traducida automáticamente

Artículo escrito por siddhanthapliyal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *