Given an array of size N. The task is to find the product of values of all possible non-empty subsets of the given array.
Examples:
Input: N = 2, arr[] = {3, 7}
Output: 441
All non empty subsets are:
3
7
3, 7
Product = 3 * 7 * 3 * 7 = 441
Input: N = 1, arr[] = {4}
Output: 4
Approach: On careful observation it can be deduced that number of occurrences of every element across all subsets is 2N-1. Therefore, in the final product, every element of the array will be multiplied to itself by 2N-1 times.
Product = a[0]2N-1*a[1]2N-1********a[N-1]2N-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 product of all elements // in all subsets int product( int a[], int n) { int ans = 1; int val = pow (2, n - 1); for ( int i = 0; i < n; i++) { ans *= pow (a[i], val); } return ans; } // Driver Code int main() { int n = 2; int a[] = { 3, 7 }; cout << product(a, n); return 0; } |
Java
// Java implementation of the approach class GFG { // Function to find product of all elements // in all subsets static int product( int a[], int n) { int ans = 1 ; int val = ( int )Math.pow( 2 , n - 1 ); for ( int i = 0 ; i < n; i++) { ans *= ( int )Math.pow(a[i], val); } return ans; } // Driver Code public static void main (String[] args) { int n = 2 ; int a[] = { 3 , 7 }; System.out.println(product(a, n)); } } // This code is contributed by AnkitRai01 |
Python3
# Python3 implementation of the approach # Function to find product of # all elements in all subsets def product(a, n): ans = 1 val = pow ( 2 , n - 1 ) for i in range (n): ans * = pow (a[i], val) return ans # Driver Code n = 2 a = [ 3 , 7 ] print (product(a, n)) # This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System; class GFG { // Function to find product of all elements // in all subsets static int product( int []a, int n) { int ans = 1; int val = ( int )Math.Pow(2, n - 1); for ( int i = 0; i < n; i++) { ans *= ( int )Math.Pow(a[i], val); } return ans; } // Driver Code public static void Main () { int n = 2; int []a = { 3, 7 }; Console.WriteLine(product(a, n)); } } // This code is contributed by anuj_67.. |
Javascript
<script> // Javascript implementation of the approach // Function to find product of all elements // in all subsets function product(a, n) { var ans = 1; var val = Math.pow(2, n - 1); for ( var i = 0; i < n; i++) { ans *= Math.pow(a[i], val); } return ans; } // Driver Code var n = 2; a = [ 3, 7 ] document.write(product(a, n)); </script> |
441
Time Complexity: O(N)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!