Dada una array arr[] que consta de N enteros positivos, la tarea es verificar si el producto de todos los elementos de la array dada arr[] es un cuadrado perfecto o no. Si se encuentra que es cierto, escriba Sí. De lo contrario, imprima No.
Ejemplos:
Entrada: arr[] = {1, 4, 100}
Salida: Sí
Explicación: El producto de todos los números es 1 x 4 x 100 = 400 que es un cuadrado perfecto. Por lo tanto, imprima «Sí».Entrada: arr[] = {1, 3}
Salida: No
Enfoque ingenuo: encuentre el producto de todos los elementos de la array e intente averiguar si se trata de un cuadrado perfecto o no. Pero el problema con este enfoque es que el producto puede ser tan grande que no podemos almacenarlo y, por lo tanto , este enfoque fallará .
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Enfoque eficiente: este enfoque se basa en la observación matemática. Un número es un cuadrado perfecto si todos los factores primos del número están elevados a potencias pares. Usaremos este concepto para encontrar si el producto es un cuadrado perfecto o no. Siga los pasos que se mencionan a continuación:
- Cree una array de frecuencias para almacenar las potencias de los factores primos.
- Comience a atravesar la array.
- Para cada elemento arr[i], use la criba de Eratóstenes para encontrar las potencias de los factores primos de arr[i] y agréguelos en la array de frecuencias.
- Después de recorrer la array, comience a recorrer la array de frecuencia .
- Si algún elemento (excepto 1) tiene una frecuencia impar , devuelve falso , de lo contrario, devuelve verdadero.
A continuación se muestra la implementación del enfoque anterior:
C++
#include <bits/stdc++.h>
using namespace std;
// Function to check if the product
// of all elements is perfect square or not
bool isPerfectSquare(vector<int>& arr)
{
// Map to store the power of prime factors
map<int, int> freq;
// Loop to implement the concept
// of Sieve of Eratosthenes
for (int x : arr) {
for (int i = 2; i <= sqrt(x); i++) {
while (x > 1 and x % i == 0) {
freq[i]++;
x /= i;
}
}
if (x >= 2)
freq[x]++;
}
// Loop to check if all the prime factors
// have even power
for (auto it = freq.begin();
it != freq.end(); it++)
if (it->second % 2)
return false;
return true;
}
// Driver code
int main()
{
vector<int> arr = { 1, 4, 100 };
isPerfectSquare(arr)
? cout << "YES\n"
: cout << "NO\n";
return 0;
}
Java
import java.util.HashMap;
class GFG {
// Function to check if the product
// of all elements is perfect square or not
public static boolean isPerfectSquare(int[] arr)
{
// Map to store the power of prime factors
HashMap<Integer, Integer> freq = new HashMap<Integer, Integer>();
// Loop to implement the concept
// of Sieve of Eratosthenes
for (int x : arr) {
for (int i = 2; i <= Math.sqrt(x); i++) {
while (x > 1 && x % i == 0) {
if (freq.containsKey(i)) {
freq.put(i, freq.get(i) + 1);
} else {
freq.put(i, 1);
}
x /= i;
}
}
if (x >= 2) {
if (freq.containsKey(x)) {
freq.put(x, freq.get(x) + 1);
} else {
freq.put(x, 1);
}
}
}
// Loop to check if all the prime factors
// have even power
for (int it : freq.values())
if (it % 2 > 0)
return false;
return true;
}
// Driver code
public static void main(String args[]) {
int[] arr = { 1, 4, 100 };
if (isPerfectSquare(arr) == true)
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by gfgking.
Python3
# Python Program to implement
# the above approach
import math
# Function to check if the product
# of all elements is perfect square or not
def isPerfectSquare(arr):
# Map to store the power of prime factors
freq = dict()
# Loop to implement the concept
# of Sieve of Eratosthenes
for x in arr:
for i in range(2, math.floor(math.sqrt(x)) + 1):
while (x > 1 and x % i == 0):
if (i in freq):
freq[i] += + 1
else:
freq[i] = 1
x = x // i
if (x >= 2):
freq[x] += 1
# Loop to check if all the prime factors
# have even power
for value in freq.values():
if (value % 2 == 1):
return False
return True
# Driver code
arr = [1, 4, 100]
print("YES") if isPerfectSquare(arr) else print("NO")
# This code is contributed by gfgking
C#
using System;
using System.Collections.Generic;
public class GFG {
// Function to check if the product
// of all elements is perfect square or not
public static bool isPerfectSquare(int[] arr)
{
// Map to store the power of prime factors
Dictionary<int, int> freq = new Dictionary<int, int>();
// Loop to implement the concept
// of Sieve of Eratosthenes
int new_x = 0;
foreach (int x in arr) {
new_x = x;
for (int i = 2; i <= Math.Sqrt(new_x); i++) {
while (new_x > 1 && x % i == 0) {
if (freq.ContainsKey(i)) {
freq[i] = freq[i] + 1;
} else {
freq.Add(i, 1);
}
new_x = new_x/i;
}
}
if (new_x >= 2) {
if (freq.ContainsKey(new_x)) {
freq[new_x] = freq[new_x] + 1;
} else {
freq.Add(new_x, 1);
}
}
}
// Loop to check if all the prime factors
// have even power
foreach (int it in freq.Values)
if (it % 2 > 0)
return false;
return true;
}
// Driver code
public static void Main(String []args) {
int[] arr = { 1, 4, 100 };
if (isPerfectSquare(arr) == true)
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to check if the product
// of all elements is perfect square or not
function isPerfectSquare(arr)
{
// Map to store the power of prime factors
let freq = new Map();
// Loop to implement the concept
// of Sieve of Eratosthenes
for (let x of arr) {
for (let i = 2; i <= Math.floor(Math.sqrt(x)); i++) {
while (x > 1 && x % i == 0) {
if (freq.has(i))
freq.set(i, freq.get(i) + 1);
else
freq.set(i, 1);
x = Math.floor(x / i);
}
}
if (x >= 2)
freq.set(x, freq.get(x) + 1)
}
// Loop to check if all the prime factors
// have even power
for (let value of freq.values()) {
if (value % 2 == 1)
return false;
}
return true;
}
// Driver code
let arr = [1, 4, 100];
isPerfectSquare(arr)
? document.write("YES" + '<br>')
: document.write("NO" + '<br>');
// This code is contributed by Potta Lokesh
</script>
YES
Complejidad de tiempo: O(N * log X) donde X es el elemento más grande de la array
Espacio auxiliar: O(N)