Given an array arr[] of N integers. The value of a subset of array A is defined as the product of all prime numbers in that subset. If there are no primes in the subset then the value of that subset is 1. The task is to calculate the product of values of all possible non-empty subsets of the given array modulus 100000007.
Examples:
Input: arr[] = {3, 7}
Output: 441
val({3}) = 3
val({7}) = 7
val({3, 7}) = 3 * 7 = 21
3 * 7 * 21 = 441
Input: arr[] = {1, 1, 1}
Output: 1
Approach: Since it is known that a number occurs 2N – 1 times in all the subsets of the given array of size N. So if a number X is prime then the contribution of X will be X * X * X * ….. * 2N – 1 time i.e.
Since 2N – 1 will also be a large number, it cannot be calculated directly. Fermat’s Theorem will be used to calculate the power here.
After that, the value of each element can be calculated easily.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include<bits/stdc++.h> using namespace std; int power(int a, int b, int mod) { int aa = 1; while(b) { if(b & 1) { aa = aa * a; aa %= mod; } a = a * a; a %= mod; b /= 2; } return aa; } // Function to return the prime subset // product of the given array int product(int A[], int n) { // Create Sieve to check whether a // number is prime or not int N = 100010; int mod = 1000000007; vector<int> prime(N, 1); prime[0] = prime[1] = 0; int i = 2; while (i * i < N) { if (prime[i]) for (int j = 2 * i; j <= N;j += i) prime[j] = 0; i += 1; } // Length of the array // Calculating 2^(n-1) % mod int t = power(2, n - 1, mod - 1); int ans = 1; for (int j = 0; j < n; j++) { int i = A[j]; // If element is prime then add // its contribution in the result if( prime[i]) { ans *= power(i, t, mod); ans %= mod; } } return ans; } // Driver code int main() { int A[] = {3, 7}; int n = sizeof(A) / sizeof(A[0]); printf("%d", product(A, n)); } // This code is contributed by Mohit Kumar |
Java
// Java implementation of the approach class GFG { static int power(int a, int b, int mod) { int aa = 1; while(b > 0) { if(b % 2 == 1) { aa = aa * a; aa %= mod; } a = a * a; a %= mod; b /= 2; } return aa; } // Function to return the prime subset // product of the given array static int product(int A[], int n) { // Create Sieve to check whether a // number is prime or not int N = 100010; int mod = 1000000007; int []prime = new int[N]; for (int j = 0; j < N; j++) { prime[j] = 1; } prime[0] = prime[1] = 0; int i = 2; while (i * i < N) { if (prime[i] == 1) for (int j = 2 * i; j < N;j += i) prime[j] = 0; i += 1; } // Length of the array // Calculating 2^(n-1) % mod int t = power(2, n - 1, mod - 1); int ans = 1; for (int j = 0; j < n; j++) { i = A[j]; // If element is prime then add // its contribution in the result if( prime[i] == 1) { ans *= power(i, t, mod); ans %= mod; } } return ans; } // Driver code public static void main (String[] args) { int A[] = {3, 7}; int n = A.length; System.out.printf("%d", product(A, n)); } } // This code is contributed by Rajput-Ji |
Python3
# Python3 implementation of the approach # Function to return the prime subset # product of the given array def product(A): # Create Sieve to check whether a # number is prime or not N = 100010 mod = 1000000007 prime = [1] * N prime[0] = prime[1] = 0 i = 2 while i * i < N: if prime[i]: for j in range(i * i, N, i): prime[j] = 0 i += 1 # Length of the array n = len(A) # Calculating 2^(n-1) % mod t = pow(2, n-1, mod-1) ans = 1 for i in A: # If element is prime then add # its contribution in the result if prime[i]: ans *= pow(i, t, mod) ans %= mod return ans # Driver code A = [3, 7] print(product(A)) |
C#
// C# implementation of the approach using System; class GFG { static int power(int a, int b, int mod) { int aa = 1; while(b > 0) { if(b % 2 == 1) { aa = aa * a; aa %= mod; } a = a * a; a %= mod; b /= 2; } return aa; } // Function to return the prime subset // product of the given array static int product(int []A, int n) { // Create Sieve to check whether a // number is prime or not int N = 100010; int mod = 1000000007; int []prime = new int[N]; for (int j = 0; j < N; j++) { prime[j] = 1; } prime[0] = prime[1] = 0; int i = 2; while (i * i < N) { if (prime[i] == 1) for (int j = 2 * i; j < N; j += i) prime[j] = 0; i += 1; } // Length of the array // Calculating 2^(n-1) % mod int t = power(2, n - 1, mod - 1); int ans = 1; for (int j = 0; j < n; j++) { i = A[j]; // If element is prime then add // its contribution in the result if( prime[i] == 1) { ans *= power(i, t, mod); ans %= mod; } } return ans; } // Driver code public static void Main(String[] args) { int []A = {3, 7}; int n = A.Length; Console.Write("{0}", product(A, n)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of the approach function power(a, b, mod) { let aa = 1; while (b) { if (b & 1) { aa = aa * a; aa %= mod; } a = a * a; a %= mod; b = Math.floor(b / 2); } return aa; } // Function to return the prime subset // product of the given array function product(A, n) { // Create Sieve to check whether a // number is prime or not let N = 100010; let mod = 1000000007; let prime = new Array(N).fill(1); prime[0] = prime[1] = 0; let i = 2; while (i * i < N) { if (prime[i]) for (let j = 2 * i; j <= N; j += i) prime[j] = 0; i += 1; } // Length of the array // Calculating 2^(n-1) % mod let t = power(2, n - 1, mod - 1); let ans = 1; for (let j = 0; j < n; j++) { let i = A[j]; // If element is prime then add // its contribution in the result if (prime[i]) { ans *= power(i, t, mod); ans %= mod; } } return ans; } // Driver code let A = [3, 7]; let n = A.length; document.write(product(A, n)); // This code is contributed by Saurabh Jaiswal </script> |
Output
441
Time Complexity: O(n), where n is the size of the given array.
Auxiliary Space: O(100010) ? O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
