Producto de todos los Subconjuntos de un conjunto formado por primeros N números naturales

Dado un número N , la tarea es encontrar el producto de todos los elementos de todos los posibles subconjuntos de un conjunto formado por primeros N números naturales.
Ejemplos: 
 

Entrada: N = 2 
Salida: 4 
Los posibles subconjuntos son {{1}, {2}, {1, 2}}. 
Producto de elementos en subconjuntos = {1} * {2} * {1 * 2} = 4
Entrada: N = 3 
Salida: 1296 
Los posibles subconjuntos son {{1}, {2}, {3}, {1, 2} , {1, 3}, {2, 3}, {1, 2, 3}} 
Producto de elementos en subconjuntos = 1 * 2 * 3 * (1 * 2) * (1 * 3) * (2 * 3) * (1 * 2 * 3) = 1296 
 

Enfoque ingenuo: una solución simple es generar todos los subconjuntos del primer número natural N. Luego, para cada subconjunto, calcule su producto y finalmente devuelva el producto general de cada subconjunto.
Enfoque eficiente: 
 

• Se puede observar que cada elemento del arreglo original aparece 2 ^{(N – 1)} veces en todos los subconjuntos.
• Por lo tanto, la contribución de cualquier elemento arr _i en la respuesta final será 
   

i * 2(N – 1)

•  
• Entonces, la Suma de cubos de todos los Subconjuntos será 
   

12N-1 * 22N-1 * 32N-1......N2N-1

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

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the product of all elements
// in all subsets in natural numbers from 1 to N
int product(int N)
{
    int ans = 1;
    int val = pow(2, N - 1);
 
    for (int i = 1; i <= N; i++) {
        ans *= pow(i, val);
    }
 
    return ans;
}
 
// Driver Code
int main()
{
    int N = 2;
 
    cout << product(N);
 
    return 0;
}

// Java implementation of the approach
class GFG {
 
    // Function to find the product of all elements
    // in all subsets in natural numbers from 1 to N
    static int product(int N)
    {
        int ans = 1;
        int val = (int)Math.pow(2, N - 1);
     
        for (int i = 1; i <= N; i++) {
            ans *= (int)Math.pow(i, val);
        }
     
        return ans;
    }
     
    // Driver Code
    public static void main (String[] args)
    {
        int N = 2;
     
        System.out.println(product(N));
    }
}
 
// This code is contributed by AnkitRai01

# Python3 implementation of the approach
 
# Function to find the product of all elements
# in all subsets in natural numbers from 1 to N
def product(N) :
    ans = 1;
    val = 2 **(N - 1);
 
    for i in range(1, N + 1) :
        ans *= (i**val);
     
    return ans;
 
 
# Driver Code
if __name__ == "__main__" :
 
    N = 2;
 
    print(product(N));
     
# This code is contributed by AnkitRai01

// C# implementation of the approach
using System;
 
class GFG {
 
    // Function to find the product of all elements
    // in all subsets in natural numbers from 1 to N
    static int product(int N)
    {
        int ans = 1;
        int val = (int)Math.Pow(2, N - 1);
     
        for (int i = 1; i <= N; i++) {
            ans *= (int)Math.Pow(i, val);
        }
     
        return ans;
    }
     
    // Driver Code
    public static void Main (string[] args)
    {
        int N = 2;
     
        Console.WriteLine(product(N));
    }
}
 
// This code is contributed by AnkitRai01

<script>
// javascript implementation of the approach
 
// Function to find the product of all elements
// in all subsets in natural numbers from 1 to N
function product( N)
{
    let ans = 1;
    let val = Math.pow(2, N - 1);
    for (let i = 1; i <= N; i++)
    {
        ans *= Math.pow(i, val);
    }
    return ans;
}
 
// Driver Code
 
    let N = 2;
    document.write(product(N));
 
// This code is contributed by todaysgaurav
 
</script>

4

Complejidad de tiempo: O(N*logN)

Espacio Auxiliar: O(1)