Comprueba si el producto de cada subsucesión es un cuadrado perfecto o no

Dada una array arr[] que consta de N enteros positivos, la tarea es verificar si el producto de los elementos de cada subsecuencia 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: Las
siguientes son las subsecuencias de la array dada arr[]:

1. {1}, el producto es igual a 1 y es un cuadrado perfecto.
2. {1, 4}, el producto es igual a 4 y es un cuadrado perfecto.
3. {1, 100}, el producto es igual a 100 y es un cuadrado perfecto.
4. {1, 4, 100}, el producto es igual a 400 y es un cuadrado perfecto.
5. {4}, el producto es igual a 4 y es un cuadrado perfecto.
6. {4, 100}, el producto es igual a 400 y es un cuadrado perfecto.
7. {100}, el producto es igual a 100 y es un cuadrado perfecto.

Por lo tanto, imprima «Sí».

Entrada: arr[] = {1, 3}
Salida: No  

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todas las subsecuencias posibles de la array dada y si los elementos del producto de cada subsecuencia son un cuadrado perfecto, entonces imprima Sí . De lo contrario , imprima No.

Complejidad temporal: O(N*2 ^N )
Espacio auxiliar: O(1)

Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando el hecho de que el producto de dos números cuadrados perfectos también será un cuadrado perfecto. Por lo tanto, para comprobar si el producto individual de los elementos de todas las subsucesiones es un cuadrado perfecto o no, la idea es comprobar si todos los elementos del arreglo son cuadrados perfectos o no. Si se encuentra que es cierto, escriba Sí . De lo contrario , imprima No.

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

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if the product of
// every subsequence of the array is a
// perfect square or not
string perfectSquare(int arr[], int N)
{
    // Traverse the given array
    for (int i = 0; i < N; i++) {
 
        // If arr[i] is a perfect
        // square or not
        int p = sqrt(arr[i]);
 
        if (p * p != arr[i]) {
            return "No";
        }
    }
 
    // Return "Yes"
    return "Yes";
}
 
// Driver Code
int main()
{
    int arr[] = { 1, 4, 100 };
    int N = sizeof(arr) / sizeof(arr[0]);
    cout << perfectSquare(arr, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG{
     
// Function to check if the product of
// every subsequence of the array is a
// perfect square or not
static String perfectSquare(int arr[], int N)
{
     
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
         
        // If arr[i] is a perfect
        // square or not
        int p = (int)Math.sqrt(arr[i]);
 
        if (p * p != arr[i])
        {
            return "No";
        }
    }
     
    // Return "Yes"
    return "Yes";
}
 
// Driver Code
public static void main (String[] args)
{
    int arr[] = { 1, 4, 100 };
    int N = arr.length;
     
    System.out.println(perfectSquare(arr, N));
}
}
 
// This code is contributed by Potta Lokesh

# Python 3 program for the above approach
from math import sqrt
 
# Function to check if the product of
# every subsequence of the array is a
# perfect square or not
def perfectSquare(arr, N):
   
    # Traverse the given array
    for i in range(N):
       
        # If arr[i] is a perfect
        # square or not
        p = sqrt(arr[i])
 
        if (p * p != arr[i]):
            return "No"
 
    # Return "Yes"
    return "Yes"
 
# Driver Code
if __name__ == '__main__':
    arr = [1, 4, 100]
    N = len(arr)
    print(perfectSquare(arr, N))
 
    # This code is contributed by ipg2016107.

// C# program for the above approach
using System;
 
class GFG{
 
// Function to check if the product of
// every subsequence of the array is a
// perfect square or not
static String perfectSquare(int[] arr, int N)
{
     
    // Traverse the given array
    for(int i = 0; i < N; i++)
    {
         
        // If arr[i] is a perfect
        // square or not
        int p = (int)Math.Sqrt(arr[i]);
 
        if (p * p != arr[i])
        {
            return "No";
        }
    }
 
    // Return "Yes"
    return "Yes";
}
 
// Driver Code
public static void Main()
{
    int[] arr = { 1, 4, 100 };
    int N = arr.Length;
 
    Console.WriteLine(perfectSquare(arr, N));
}
}
 
// This code is contributed by subham348

<script>
 
// Javascript program for the above approach
 
// Function to check if the product of
// every subsequence of the array is a
// perfect square or not
function perfectSquare(arr, N)
{
     
    // Traverse the given array
    for(let i = 0; i < N; i++)
    {
         
        // If arr[i] is a perfect
        // square or not
        let p = Math.sqrt(arr[i]);
 
        if (p * p != arr[i])
        {
            return "No";
        }
    }
     
    // Return "Yes"
    return "Yes";
}
 
// Driver Code
let arr = [ 1, 4, 100 ];
let N = arr.length;
 
document.write(perfectSquare(arr, N));
 
// This code is contributed by target_2
 
</script>

Yes

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