Dada una array arr[] que contiene enteros positivos, la tarea es encontrar el número mínimo de operaciones que se deben realizar en la array para convertir cada número de la array en una superpotencia.
En cada operación, podemos multiplicar cualquier elemento de la array con un número entero.
Una superpotencia se define como un número en la array que, cuando se multiplica por cualquier otro número en la array, aparte de sí mismo, forma un cuadrado perfecto.
Ejemplos:
Entrada: arr[] = {2, 2, 2}
Salida: 0
Explicación:
No necesitamos realizar ninguna operación en la array porque al seleccionar cualquier elemento (2) y multiplicarlo con cualquier elemento en algún otro índice (2 ), obtenemos un cuadrado perfecto (4).
Entrada: arr[] = {2, 4, 6}
Salida: 2
Explicación:
Necesitamos realizar las siguientes dos operaciones:
Primero, multiplicamos el elemento en el índice 1 con el número entero 2. La array se convierte en {2, 8, 6} .
En segundo lugar, multiplicamos el elemento en el índice 2 con el número entero 3. La array se convierte en {2, 8, 18}.
Ahora, todos los elementos se han convertido en una superpotencia. La multiplicación de dos números cualquiera de la array da un cuadrado perfecto.
Es decir, 2 * 8 = 16, 2 * 16 = 36 y 8 * 18 = 144.
Enfoque: Dado que necesitamos comprobar los factores primos de todos los números, la idea es precalcular primero los factores primos únicos de todos los números y almacenarlos en un hashmap . Luego, creamos una variable para almacenar la cantidad de veces que aparece el factor primo en cada elemento de la array. También debemos observar que necesitamos encontrar el número mínimo de pasos para convertir la array. Por lo tanto, calculamos el número de impares en el vector y el número de factores primos pares, y el que sea el mínimo, esa será la respuesta. Se pueden calcular los siguientes pasos para encontrar la respuesta:
- Primero necesitamos calcular la array spf[]. Esta es la array en la que se almacena el factor primo más pequeño para todos los elementos.
- Luego, necesitamos encontrar los factores primos únicos y almacenarlos en el mapa hash.
- Ahora, recorra el mapa hash para encontrar los factores primos únicos de un número e itere sobre los elementos en la array dada para calcular la frecuencia de los factores primos.
- Ahora, se inicializan dos variables que almacenan la frecuencia del número primo cuya ocurrencia es par y otra que almacena la frecuencia de los números primos que es impar.
- Ahora, necesitamos sumar el mínimo de las dos variables en nuestra variable final, que es la operación mínima para obtener el superpoder de ese número primo.
- Repita los pasos anteriores para todos los números de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the minimum
// number of steps to modify the
// array such that the product
// of any two numbers in the
// array is a perfect square
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
// Function to find the smallest
// prime factor of the elements
void spf_array(int spf[])
{
// Initializing the first element
// of the array
spf[1] = 1;
// Loop to add the remaining
// elements to the array
for (int i = 2; i < 1000; i++)
// Marking the smallest prime
// factor for every
// number to be itself
spf[i] = i;
// Separately marking spf for
// every even number as 2
for (int i = 4; i < 1000; i += 2)
spf[i] = 2;
for (int i = 3; i * i < 1000; i++) {
// Checking if i is prime
if (spf[i] == i) {
// Marking SPF for all the
// numbers divisible by i
for (int j = i * i; j < 1000; j += i)
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find the minimum
// number of steps to modify the
// array such that the product
// of any two numbers in the
// array is a perfect square
int minimum_operation(int b[], int d,
int spf[])
{
// Map created to store
// the unique prime numbers
unordered_map<int, int> m;
int i = 0;
// Variable to store the
// minimum number of operations
int c = 0;
// Loop to store every
// unique prime number
for (i = 0; i < d; i++) {
int x = b[i];
while (x != 1) {
x = x / spf[x];
if (m[spf[x]] == 0) {
m[spf[x]] = 1;
}
}
}
// Erasing 1 as a key because
// it is not a prime number
m.erase(1);
// Iterating through the hash
for (auto x : m) {
// Two variables used for
// counting the frequency
// of prime is even or odd
int e = 0, o = 0;
// First prime number
int j = x.first;
// Iterating the number D
for (i = 0; i < d; i++) {
// check if prime is a
// factor of the element
// in the array
if (b[i] % j == 0) {
int h = 0;
int g = b[i];
// Loop for calculating the
// frequency of the element
while (g != 0) {
if (g % j != 0) {
break;
}
g = g / j;
h = h + 1;
}
// Check for frequency
// odd or even
if (h % 2 == 0) {
e = e + 1;
}
else {
o = o + 1;
}
}
else {
// If it is not a factor of the
// element, then it is automatically
// even
e = e + 1;
}
}
// Storing the minimum of two variable
// even or odd
c = c + min(o, e);
}
return c;
}
// Driver code
int main()
{
int spf[1001];
// Input array
int b[] = { 1, 4, 6 };
// Creating shortest prime
// factorisation array
int d = sizeof(b) / sizeof(b[0]);
spf_array(spf);
cout << minimum_operation(b, d, spf)
<< endl;
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to find the smallest
// prime factor of the elements
static void spf_array(int spf[])
{
// Initializing the first element
// of the array
spf[1] = 1;
// Loop to add the remaining
// elements to the array
for(int i = 2; i < 1000; i++)
// Marking the smallest prime
// factor for every
// number to be itself
spf[i] = i;
// Separately marking spf for
// every even number as 2
for(int i = 4; i < 1000; i += 2)
spf[i] = 2;
for(int i = 3; i * i < 1000; i++)
{
// Checking if i is prime
if (spf[i] == i)
{
// Marking SPF for all the
// numbers divisible by i
for(int j = i * i; j < 1000; j += i)
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find the minimum
// number of steps to modify the
// array such that the product
// of any two numbers in the
// array is a perfect square
static int minimum_operation(int b[], int d,
int spf[])
{
// Map created to store
// the unique prime numbers
Map<Integer, Integer> m=new HashMap<>();
int i = 0;
// Variable to store the
// minimum number of operations
int c = 0;
// Loop to store every
// unique prime number
for(i = 0; i < d; i++)
{
int x = b[i];
while (x != 1)
{
x = x / spf[x];
if (m.get(spf[x]) == null)
{
m.put(spf[x],1);
}
}
}
// Erasing 1 as a key because
// it is not a prime number
m.remove(1);
// Iterating through the hash
for(Map.Entry<Integer,
Integer> x : m.entrySet())
{
// Two variables used for
// counting the frequency
// of prime is even or odd
int e = 0, o = 0;
// First prime number
int j = x.getKey();
// Iterating the number D
for(i = 0; i < d; i++)
{
// Check if prime is a
// factor of the element
// in the array
if (b[i] % j == 0)
{
int h = 0;
int g = b[i];
// Loop for calculating the
// frequency of the element
while (g != 0)
{
if (g % j != 0)
{
break;
}
g = g / j;
h = h + 1;
}
// Check for frequency
// odd or even
if (h % 2 == 0)
{
e = e + 1;
}
else
{
o = o + 1;
}
}
else
{
// If it is not a factor of the
// element, then it is automatically
// even
e = e + 1;
}
}
// Storing the minimum of two variable
// even or odd
c = c + Math.min(o, e);
}
return c;
}
// Driver Code
public static void main (String[] args)
{
int[] spf = new int[1001];
// Input array
int b[] = { 1, 4, 6 };
// Creating shortest prime
// factorisation array
int d = b.length;
spf_array(spf);
System.out.print(minimum_operation(b, d, spf));
}
}
// This code is contributed by offbeat
Python3
# Python program to find the minimum # number of steps to modify the # array such that the product # of any two numbers in the # array is a perfect square # Function to find the smallest # prime factor of the elements def spf_array(spf): # Initializing the first element # of the array spf[1] = 1; # Loop to add the remaining # elements to the array for i in range(2, 1000): # Marking the smallest prime # factor for every # number to be itself spf[i] = i; # Separately marking spf for # every even number as 2 for i in range(4, 1000, 2): spf[i] = 2; for i in range(3, (int)(1000 ** 0.5), 1): # Checking if i is prime if (spf[i] == i): # Marking SPF for all the # numbers divisible by i for j in range(i * i, 1000, i): # Marking spf[j] if it is not # previously marked if (spf[j] == j): spf[j] = i; # Function to find the minimum # number of steps to modify the # array such that the product # of any two numbers in the # array is a perfect square def minimum_operation( b, d, spf) : # Map created to store # the unique prime numbers m = dict(); i = 0; # Variable to store the # minimum number of operations c = 0; # Loop to store every # unique prime number for i in range(d): x = b[i]; while (x != 1): x = (x // spf[x]); if (spf[x] not in m): m[spf[x]] = 1 # Erasing 1 as a key because # it is not a prime number m.pop(1); # Iterating through the hash for key in m.keys(): # Two variables used for # counting the frequency # of prime is even or odd e = 0 o = 0 # First prime number j = key; # Iterating the number D for i in range(d): # check if prime is a # factor of the element # in the array if (b[i] % j == 0): h = 0; g = b[i]; # Loop for calculating the # frequency of the element while (g != 0): if (g % j != 0): break; g = g // j h = h + 1; # Check for frequency # odd or even if (h % 2 == 0): e = e + 1; else : o = o + 1; else: # If it is not a factor of the # element, then it is automatically # even e = e + 1; # Storing the minimum of two variable # even or odd c = c + min(o, e); return c; # Driver code spf = [0] * (1001) # Input array b = [1, 4, 6 ]; # Creating shortest prime # factorisation array d = len(b); spf_array(spf); print( minimum_operation(b, d, spf) ); # This code is contributed by entertain2022.
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to find the smallest
// prime factor of the elements
static void spf_array(int []spf)
{
// Initializing the first element
// of the array
spf[1] = 1;
// Loop to add the remaining
// elements to the array
for(int i = 2; i < 1000; i++)
// Marking the smallest prime
// factor for every
// number to be itself
spf[i] = i;
// Separately marking spf for
// every even number as 2
for(int i = 4; i < 1000; i += 2)
spf[i] = 2;
for(int i = 3; i * i < 1000; i++)
{
// Checking if i is prime
if (spf[i] == i)
{
// Marking SPF for all the
// numbers divisible by i
for(int j = i * i; j < 1000; j += i)
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find the minimum
// number of steps to modify the
// array such that the product
// of any two numbers in the
// array is a perfect square
static int minimum_operation(int []b,
int d, int []spf)
{
// Map created to store
// the unique prime numbers
Dictionary<int,
int> m = new Dictionary<int,
int>();
int i = 0;
// Variable to store the
// minimum number of operations
int c = 0;
// Loop to store every
// unique prime number
for(i = 0; i < d; i++)
{
int x = b[i];
while (x != 1)
{
x = x / spf[x];
if (!m.ContainsKey(spf[x]))
{
m.Add(spf[x], 1);
}
}
}
// Erasing 1 as a key because
// it is not a prime number
m.Remove(1);
// Iterating through the hash
foreach(KeyValuePair<int,
int> x in m)
{
// Two variables used for
// counting the frequency
// of prime is even or odd
int e = 0, o = 0;
// First prime number
int j = x.Key;
// Iterating the number D
for(i = 0; i < d; i++)
{
// Check if prime is a
// factor of the element
// in the array
if (b[i] % j == 0)
{
int h = 0;
int g = b[i];
// Loop for calculating the
// frequency of the element
while (g != 0)
{
if (g % j != 0)
{
break;
}
g = g / j;
h = h + 1;
}
// Check for frequency
// odd or even
if (h % 2 == 0)
{
e = e + 1;
}
else
{
o = o + 1;
}
}
else
{
// If it is not a factor of the
// element, then it is automatically
// even
e = e + 1;
}
}
// Storing the minimum of two variable
// even or odd
c = c + Math.Min(o, e);
}
return c;
}
// Driver Code
public static void Main(String[] args)
{
int[] spf = new int[1001];
// Input array
int []b = {1, 4, 6};
// Creating shortest prime
// factorisation array
int d = b.Length;
spf_array(spf);
Console.Write(minimum_operation(b, d, spf));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program to find the minimum
// number of steps to modify the
// array such that the product
// of any two numbers in the
// array is a perfect square
// Function to find the smallest
// prime factor of the elements
function spf_array(spf)
{
// Initializing the first element
// of the array
spf[1] = 1;
// Loop to add the remaining
// elements to the array
for (var i = 2; i < 1000; i++)
// Marking the smallest prime
// factor for every
// number to be itself
spf[i] = i;
// Separately marking spf for
// every even number as 2
for (var i = 4; i < 1000; i += 2)
spf[i] = 2;
for (var i = 3; i * i < 1000; i++) {
// Checking if i is prime
if (spf[i] == i) {
// Marking SPF for all the
// numbers divisible by i
for (var j = i * i; j < 1000; j += i)
// Marking spf[j] if it is not
// previously marked
if (spf[j] == j)
spf[j] = i;
}
}
}
// Function to find the minimum
// number of steps to modify the
// array such that the product
// of any two numbers in the
// array is a perfect square
function minimum_operation( b, d, spf)
{
// Map created to store
// the unique prime numbers
var m = new Map();
var i = 0;
// Variable to store the
// minimum number of operations
var c = 0;
// Loop to store every
// unique prime number
for (i = 0; i < d; i++) {
var x = b[i];
while (x != 1) {
x = parseInt(x / spf[x]);
if (!m.has(spf[x])) {
m.set(spf[x], 1);
}
}
}
// Erasing 1 as a key because
// it is not a prime number
m.delete(1);
// Iterating through the hash
m.forEach((value, key) => {
// Two variables used for
// counting the frequency
// of prime is even or odd
var e = 0, o = 0;
// First prime number
var j = key;
// Iterating the number D
for (i = 0; i < d; i++) {
// check if prime is a
// factor of the element
// in the array
if (b[i] % j == 0) {
var h = 0;
var g = b[i];
// Loop for calculating the
// frequency of the element
while (g != 0) {
if (g % j != 0) {
break;
}
g = parseInt(g / j);
h = h + 1;
}
// Check for frequency
// odd or even
if (h % 2 == 0) {
e = e + 1;
}
else {
o = o + 1;
}
}
else {
// If it is not a factor of the
// element, then it is automatically
// even
e = e + 1;
}
}
// Storing the minimum of two variable
// even or odd
c = c + Math.min(o, e);
});
return c;
}
// Driver code
var spf = Array(1001)
// Input array
var b = [1, 4, 6 ];
// Creating shortest prime
// factorisation array
var d = b.length;
spf_array(spf);
document.write( minimum_operation(b, d, spf) );
</script>
Producción:
2
Complejidad de tiempo: O(N * log(N)) , donde N es el tamaño de la array de entrada.
Publicación traducida automáticamente
Artículo escrito por vabzcode12 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA