Product of all Subsets of a set formed by first N natural numbers
Given a number N, the task is to find the product of all the elements from all possible subsets of a set formed by first N natural numbers.
Examples:
Input: N = 2
Output: 4
Possible subsets are {{1}, {2}, {1, 2}}.
Product of elements in subsets = {1} * {2} * {1 * 2} = 4
Input: N = 3
Output: 1296
Possible subsets are {{1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
Product of elements in subsets = 1 * 2 * 3 * (1 * 2) * (1 * 3) * (2 * 3) * (1 * 2 * 3) = 1296
Naive Approach: A simple solution is to generate all subsets of first N natural number. Then for every subset, compute its product and finally return overall product of each subset.
Efficient Approach:
- It can be observed that each element of the original array appears in 2(N – 1) times in all subsets.
- Therefore contribution of any element arri in the final answer will be
i * 2(N – 1)
- So, the Sum of cubes of all Subsets will be
12N-1 * 22N-1 * 32N-1......N2N-1
Below is the implementation of the above approach:
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
Time Complexity: O(N*logN)
Auxiliary Space: O(1)