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++
// 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
// 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
# 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#
// 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
Javascript
<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)