Comprobar si el producto de una array que contiene números primos es un cuadrado perfecto

Dada una array arr[] que contiene solo números primos, la tarea es verificar si el producto de los elementos de la array es un cuadrado perfecto o no.
Ejemplos: 
 

Entrada: arr[] = {2, 2, 7, 7} 
Salida: Sí 
2 * 2 * 7 * 7 = 196 = 14 ²
Entrada: arr[] = {3, 3, 3, 5, 5} 
Salida: No 
 

Enfoque ingenuo: Multiplique todos los elementos de la array y verifique si el producto es un cuadrado perfecto o no.
Enfoque eficiente: cuente las frecuencias de todos los elementos de la array, si la frecuencia de todos los elementos es par, entonces el producto será un cuadrado perfecto; de lo contrario, imprima No.
A continuación se muestra la implementación del enfoque anterior: 
 

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function that returns true if
// the product of all the array elements
// is a perfect square
bool isPerfectSquare(int arr[], int n)
{
    unordered_map<int, int> umap;
 
    // Update the frequencies of
    // all the array elements
    for (int i = 0; i < n; i++)
        umap[arr[i]]++;
 
    unordered_map<int, int>::iterator itr;
    for (itr = umap.begin(); itr != umap.end(); itr++)
 
        // If frequency of some element
        // in the array is odd
        if ((itr->second) % 2 == 1)
            return false;
 
    return true;
}
 
// Driver code
int main()
{
    int arr[] = { 2, 2, 7, 7 };
    int n = sizeof(arr) / sizeof(arr[0]);
 
    if (isPerfectSquare(arr, n))
        cout << "Yes";
    else
        cout << "No";
 
    return 0;
}

// Java implementation of the approach
import java.util.*;
 
class GFG
{
    // Function that returns true if
    // the product of all the array elements
    // is a perfect square
    static boolean isPerfectSquare(int [] arr, int n)
    {
         
        HashMap<Integer, Integer> umap = new HashMap<>();
         
        // Update the frequencies of
        // all the array elements
        for (int i = 0; i < n; i++)
        {
            if(umap.containsKey(arr[i]))
                umap.put(arr[i], umap.get(arr[i]) + 1 );
            else
                umap.put(arr[i], 1);
             
        }
         
        Iterator<Map.Entry<Integer, Integer> >
                iterator = umap.entrySet().iterator();
 
        while(iterator.hasNext())
        {
            Map.Entry<Integer, Integer> entry = iterator.next();
             
            // If frequency of some element
            // in the array is odd
            if (entry.getValue() % 2 == 1)
                return false;
        }
        return true;
    }
     
    // Driver code
    public static void main (String[] args)
    {
 
        int arr [] = { 2, 2, 7, 7 };
        int n = arr.length;
     
        if (isPerfectSquare(arr, n))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}
 
// This code is contributed by ihritik

# Python3 implementation of the approach
 
# Function that returns true if
# the product of all the array elements
# is a perfect square
def isPerfectSquare(arr, n) :
 
    umap = dict.fromkeys(arr, n);
 
    # Update the frequencies of
    # all the array elements
    for key in arr :
        umap[key] += 1;
 
    for key in arr :
 
        # If frequency of some element
        # in the array is odd
        if (umap[key] % 2 == 1) :
            return False;
 
    return True;
 
# Driver code
if __name__ == "__main__" :
 
    arr = [ 2, 2, 7, 7 ];
    n = len(arr)
 
    if (isPerfectSquare(arr, n)) :
        print("Yes");
    else :
        print("No");
 
# This code is contributed by Ryuga

// C# implementation of the approach
using System;
using System.Collections.Generic;
 
class GFG
{
    // Function that returns true if
    // the product of all the array elements
    // is a perfect square
    static bool isPerfectSquare(int [] arr, int n)
    {
         
        Dictionary<int, int> umap = new Dictionary<int, int>();
         
        // Update the frequencies of
        // all the array elements
        for (int i = 0; i < n; i++)
        {
            if(umap.ContainsKey(arr[i]))
                umap[arr[i]]++;
            else
                umap[arr[i]] = 1;
             
        }
         
        Dictionary<int, int>.ValueCollection valueColl =
                                                umap.Values;
        foreach(int val in valueColl)
        {
            // If frequency of some element
            // in the array is odd
            if (val % 2 == 1)
                return false;
        }
        return true;
    }
     
    // Driver code
    public static void Main ()
    {
 
        int [] arr = { 2, 2, 7, 7 };
        int n = arr.Length;
     
        if (isPerfectSquare(arr, n))
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
}
 
// This code is contributed by ihritik

<script>
// Javascript implementation of the approach
 
// Function that returns true if
// the product of all the array elements
// is a perfect square
function isPerfectSquare(arr, n)
{
    let umap = new Map();
 
    // Update the frequencies of
    // all the array elements
    for (let i = 0; i < n; i++){
        umap[arr[i]]++;
        if(umap.has(arr[i])){
            umap.set(arr[i], umap.get(arr[i]) + 1)
        }else{
            umap.set(arr[i], 1)
        }
    }
 
    for (let itr of umap)
 
        // If frequency of some element
        // in the array is odd
        if ((itr[1]) % 2 == 1)
            return false;
 
    return true;
}
 
// Driver code
    let arr = [ 2, 2, 7, 7 ];
    let n = arr.length;
 
    if (isPerfectSquare(arr, n))
        document.write("Yes");
    else
        document.write("No");
 
// This code is contributed by _saurabh_jaiswal
</script>

Yes

Complejidad de tiempo: O(n)

Espacio Auxiliar: O(n)