Producto de todos los subarreglos no repetidos de un arreglo

Dada una array que contiene distintos enteros arr[] de tamaño N , la tarea es imprimir el producto de todos los subarreglos no repetidos de la array. 
Ejemplos: 
 

Entrada: array[] = {2, 4} 
Salida: 64 
Explicación: 
Los posibles subarreglos para la array dada son {2}, {2, 4}, {4} 
Los productos son 2, 8, 4 respectivamente. Por lo tanto, el producto total de todos los subarreglos = 64
Entrada: array[] = {10, 3, 7} 
Salida: 1944810000 
Explicación: 
Los posibles subarreglos para el arreglo dado son {10}, {10, 3}, {0, 7}, {10, 3, 7}, {3}, {7}, {3, 7}. 
Los productos son 10, 30, 70, 210, 3, 7, 21 respectivamente. Por lo tanto, el producto total de todos los subarreglos = 1944810000 
 

Enfoque ingenuo: el enfoque ingenuo para este problema es generar todos los subconjuntos del conjunto dado y calcular su producto. La complejidad temporal de este enfoque es exponencial. 
Enfoque Eficiente: La idea es hacer una observación. Si observamos los subconjuntos que no se repiten, podemos observar que las ocurrencias de un solo elemento en los subconjuntos siguen una relación con la longitud del conjunto. 
 

• Por ejemplo, deje que la array arr[] = {10, 3, 7}.
• Todos los posibles subarreglos no repetitivos de la array anterior son: {{10}, {10, 3}, {10, 7}, {10, 3, 7}, {3}, {7}, {3, 7} }.
• En los subconjuntos anteriores, la frecuencia de cada elemento se puede observar como: 
   

Frequency of 10 in subarrays = 4
Frequency of 3 in subarrays = 4
Frequency of 7 in subarrays = 4

• Aquí, la siguiente identidad se cumple para las arrays de cualquier longitud: 
   

Frequency of element = 2(arr.length-1)

• Por lo tanto, para obtener el producto final, simplemente podemos realizar: 
   

product = 10 * (freq_of_10) * 3 * (freq_of_3) * 7 * (freq_of_7)

• Por lo tanto, la idea es simplemente iterar a través de la array y realizar la multiplicación de cada elemento y su frecuencia correspondiente.

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

// C++ program to find the product of
// all non-repeating Subarrays of an Array
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the product of
// all non-repeating Subarrays of an Array
long product(int arr[], int n)
{
     
    // Finding the occurrence of every element
    double occurrence = pow(2, n - 1);
 
    double product = 1;
 
    // Iterating through the array and
    // finding the product
    for(int i = 0; i < n; i++)
    {
         
        // We are taking the power of each
        // element in array with the occurrence
        // and then taking product of those.
        product *= pow(arr[i], occurrence);
    }
    return (long)product;
}
 
// Driver code
int main()
{
    int arr[] = { 10, 3, 7 };
     
    int len = sizeof(arr) / sizeof(arr[0]);
     
    cout << product(arr, len);
    return 0;
}
 
// This code is contributed by PrinciRaj1992

// Java program to find the product of
// all non-repeating Subarrays of an Array
 
public class GFG {
 
    // Function to find the product of
    // all non-repeating Subarrays of an Array
    private static long product(int[] arr)
    {
        // Finding the occurrence of every element
        double occurrence = Math.pow(2, arr.length - 1);
 
        double product = 1;
 
        // Iterating through the array and
        // finding the product
        for (int i = 0; i < arr.length; i++) {
 
            // We are taking the power of each
            // element in array with the occurrence
            // and then taking product of those.
            product *= Math.pow(arr[i], occurrence);
        }
 
        return (long)product;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 10, 3, 7 };
 
        System.out.println(product(arr));
    }
}

# Python3 program to find the product of
# all non-repeating Subarrays of an Array
 
# Function to find the product of
# all non-repeating Subarrays of an Array
def product(arr):
 
    # Finding the occurrence of every element
    occurrence = pow(2, len(arr) - 1);
 
    product = 1;
 
    # Iterating through the array and
    # finding the product
    for i in range(0, len(arr)):
 
        # We are taking the power of each
        # element in array with the occurrence
        # and then taking product of those.
        product *= pow(arr[i], occurrence);
     
    return product;
 
# Driver code
arr = [ 10, 3, 7 ];
print(product(arr));
 
# This code is contributed by Code_Mech

// C# program to find the product of
// all non-repeating Subarrays of an Array
using System;
class GFG{
 
// Function to find the product of
// all non-repeating Subarrays of an Array
private static long product(int[] arr)
{
    // Finding the occurrence of every element
    double occurrence = Math.Pow(2, arr.Length - 1);
 
    double product = 1;
 
    // Iterating through the array and
    // finding the product
    for (int i = 0; i < arr.Length; i++)
    {
 
        // We are taking the power of each
        // element in array with the occurrence
        // and then taking product of those.
        product *= Math.Pow(arr[i], occurrence);
    }
    return (long)product;
}
 
// Driver code
public static void Main(String[] args)
{
    int[] arr = { 10, 3, 7 };
 
    Console.WriteLine(product(arr));
}
}
 
// This code is contributed by amal kumar choubey

<script>
 
// Javascript program to find the product of
// all non-repeating Subarrays of an Array
 
    // Function to find the product of
    // all non-repeating Subarrays of an Array
    function product(arr)
    {
        // Finding the occurrence of every element
        let occurrence = Math.pow(2, arr.length - 1);
   
        let product = 1;
   
        // Iterating through the array and
        // finding the product
        for (let i = 0; i < arr.length; i++) {
   
            // We are taking the power of each
            // element in array with the occurrence
            // and then taking product of those.
            product *= Math.pow(arr[i], occurrence);
        }
   
        return product;
    }
 
 
// Driver Code
     
    let arr = [ 10, 3, 7 ];
   
    document.write(product(arr));
       
</script>

1944810000

Complejidad de tiempo: O(N) , donde N es el tamaño de la array 
Espacio auxiliar: O(1)