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:
- Inicialice un Mapa para almacenar todos los números de anagrama correspondientes a los números cuyos dígitos están ordenados.
- Genere todos los cuadrados perfectos de longitud K.
- Para cada cuadrado perfecto generado, inserte el número en el Mapa correspondiente al número cuyo dígito está ordenado en orden ascendente.
- 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;
}
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