Given an array arr[] of size N. The task is to find a number of subsets whose product can be represented as a product of one or more distinct prime numbers. Modify your answer to the modulo of 109 + 7.
Example:
Input: N = 4, arr[] = {1, 2, 3, 4}
Output: 6
Explanation: The good subsets are:
- [1, 2]: product is 2, which is the product of distinct prime 2.
- [1, 2, 3]: product is 6, which is the product of distinct primes 2 and 3.
- [1, 3]: product is 3, which is the product of distinct prime 3.
- [2]: product is 2, which is the product of distinct prime 2.
- [2, 3]: product is 6, which is the product of distinct primes 2 and 3.
- [3]: product is 3, which is the product of distinct prime 3.
Input: N = 3, arr[] = {2, 2, 3}
Output: 5
Explanation: The good subsets are : {2}, {2}, {2, 3}, {2, 3}, {3}
Approach: This can be solved with the following idea:
The general approach for the given problem is to use dynamic programming to count the number of good subsets.
Below are the steps involved in the implementation of the code:
- Create a static array map with a size of 31, along with a constant mod of 109 + 7.
- Find the prime factors of each integer i from 2 to 30 and set the associated bits in map[i] if i is not a multiple of 4 or 9 or equal to 25.
- Set the first member of the integer array dp to 1 and initialize the integer variables one and cnt to have sizes of 1024 and 31, respectively Step 4: If the appropriate map[i] value is non-zero and the integer i is not 1, increment one for each integer i in the provided array arr; otherwise, increment the count of i in the cnt array.
- For each index, i in the cnt array where the value is non-zero, iterate through all the possible subsets of prime numbers using a nested loop over all the possible j values from 0 to 1023. If the jth bit is set and the map[i]th bit is also set, skip to the next j. Otherwise, update the dp[j| map[i]] value with the sum of its current value and the product of the count of i and the dp[j] value.
- After the loops are complete, initialize a long variable res as 0, iterate through all the elements of the dp array, and update the res value as the sum of its current value and the current element’s value. Then decrement res by 1.
- If the one value is non-zero, calculate its power using a helper function pow and multiply the result with res. Finally, return the result as an i integer.
Below is the code implementation of the above method:
C++
// C++ code of the above approach#include <bits/stdc++.h>using namespace std;#define mod 1000000007int map_[31];// Function to calculate powerlong long pow(int n){ long long res = 1, m = 2; while (n != 0) { if ((n & 1) == 1) res = (res * m) % mod; m = m * m % mod; n >>= 1; } return res;}// Check for prime valuevoid check_prime_val(){ int prime[] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; for (int i = 2; i <= 30; ++i) { // If num is a multiple of // 4/9/25, adding it to any // subset will make it bad if (i % 4 == 0 || i % 9 == 0 || i == 25) continue; int mask = 0; for (int j = 0; j < 10; ++j) { if (i % prime[j] == 0) mask |= 1 << j; } map_[i] = mask; }}int goodSubsets(int arr[], int n){ int one = 0; // dp[set_of_primes] represents // the number of times set_of_primes // can be formed (set_of_primes === // mask) Since there are 10 possible // prime numbers, there are 2^10 // possible set_of_primes int dp[1024] = { 0 }, cnt[31] = { 0 }; dp[0] = 1; for (int i = 0; i < n; i++) { if (arr[i] == 1) one++; else if (map_[arr[i]] != 0) cnt[arr[i]]++; } for (int i = 0; i < 31; ++i) { if (cnt[i] == 0) continue; for (int j = 0; j < 1024; ++j) { if ((j & map_[i]) != 0) continue; dp[j | map_[i]] = (dp[j | map_[i]] + dp[j] * cnt[i]) % mod; } } long res = 0; for (int i : dp) res = (res + i) % mod; res--; if (one != 0) res = res * pow(one) % mod; return res;}// Driver codeint main(){ int arr[] = { 1, 2, 3, 4 }; int n = sizeof(arr) / sizeof(arr[0]); check_prime_val(); // Function call cout << goodSubsets(arr, n) << endl; return 0;}// This code is contributed by Tapesh(tapeshdua420) |
Java
// Java code of the above approachclass Solution { static int mod = (int)1e9 + 7; static int[] map = new int[31]; // Check for prime value static { int[] prime = new int[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; for (int i = 2; i <= 30; ++i) { // If num is a multiple of // 4/9/25, adding it to any // subset will make it bad if (0 == i % 4 || 0 == i % 9 || 25 == i) continue; int mask = 0; for (int j = 0; j < 10; ++j) { if (0 == i % prime[j]) mask |= 1 << j; } map[i] = mask; } } public int goodSubsets(int[] arr, int n) { int one = 0; // dp[set_of_primes] represents // the number of times set_of_primes // can be formed (set_of_primes === // mask) Since there are 10 possible // prime numbers, there are 2^10 // possible set_of_primes int[] dp = new int[1024], cnt = new int[31]; dp[0] = 1; for (int i : arr) { if (i == 1) one++; else if (map[i] != 0) cnt[i]++; } for (int i = 0; i < 31; ++i) { if (cnt[i] == 0) continue; for (int j = 0; j < 1024; ++j) { if (0 != (j & map[i])) continue; dp[j | map[i]] = (int)((dp[j | map[i]] + dp[j] * (long)cnt[i]) % mod); } } long res = 0; for (int i : dp) res = (res + i) % mod; res--; if (one != 0) res = res * pow(one) % mod; return (int)res; } // Function to calculate power public long pow(int n) { long res = 1, m = 2; while (n != 0) { if (1 == (n & 1)) res = (res * m) % mod; m = m * m % mod; n >>= 1; } return res; } // Driver code public static void main(String[] args) { int[] arr = { 1, 2, 3, 4 }; int n = arr.length; Solution solution = new Solution(); // Function call int result = solution.goodSubsets(arr, n); System.out.println(result); }} |
Python3
# Python3 code of the above approachfrom typing import Listclass Solution: mod = int(1e9 + 7) map = [0] * 31 # Check for prime value @staticmethod def calculatePrimes(): prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] for i in range(2, 31): if i % 4 == 0 or i % 9 == 0 or i == 25: continue mask = 0 for j in range(10): if i % prime[j] == 0: mask |= (1 << j) Solution.map[i] = mask def goodSubsets(self, arr: List[int], n: int) -> int: one = 0 dp = [0] * 1024 cnt = [0] * 31 dp[0] = 1 for i in arr: if i == 1: one += 1 elif Solution.map[i] != 0: cnt[i] += 1 for i in range(31): if cnt[i] == 0: continue for j in range(1024): if j & Solution.map[i]: continue dp[j | Solution.map[i]] = ( dp[j | Solution.map[i]] + dp[j] * cnt[i]) % Solution.mod res = 0 for i in dp: res = (res + i) % Solution.mod res -= 1 if one != 0: pow_val = 1 m = 2 while one != 0: if one & 1: pow_val = (pow_val * m) % Solution.mod m = (m * m) % Solution.mod one >>= 1 res = (res * pow_val) % Solution.mod return int(res) # Driver code def main(self): arr = [1, 2, 3, 4] n = len(arr) # Calculate primes Solution.calculatePrimes() # Create an instance of the class solution = Solution() # Function call result = solution.goodSubsets(arr, n) print(result)# Create an instance of the Solution classsolution = Solution()# Call the main functionsolution.main()# This code is contributed by shivamgupta0987654321 |
C#
// c# code for above approachusing System;class Program { const int mod = 1000000007; static int[] map_ = new int[31]; // Function to calculate power static long Pow(int n) { long res = 1; long m = 2; while (n != 0) { if ((n & 1) == 1) res = (res * m) % mod; m = (m * m) % mod; n >>= 1; } return res; } // Check for prime value static void CheckPrimeVal() { int[] prime = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 }; for (int i = 2; i <= 30; ++i) { // If num is a multiple of // 4/9/25, adding it to any // subset will make it bad if (i % 4 == 0 || i % 9 == 0 || i == 25) continue; int mask = 0; for (int j = 0; j < 10; ++j) { if (i % prime[j] == 0) mask |= 1 << j; } map_[i] = mask; } } static int GoodSubsets(int[] arr, int n) { int one = 0; // dp[set_of_primes] represents // the number of times set_of_primes // can be formed (set_of_primes === // mask) Since there are 10 possible // prime numbers, there are 2^10 // possible set_of_primes int[] dp = new int[1024]; int[] cnt = new int[31]; dp[0] = 1; for (int i = 0; i < n; i++) { if (arr[i] == 1) one++; else if (map_[arr[i]] != 0) cnt[arr[i]]++; } for (int i = 0; i < 31; ++i) { if (cnt[i] == 0) continue; for (int j = 0; j < 1024; ++j) { if ((j & map_[i]) != 0) continue; dp[j | map_[i]] = (dp[j | map_[i]] + dp[j] * cnt[i]) % mod; } } long res = 0; foreach(int i in dp) res = (res + i) % mod; res--; if (one != 0) res = (res * Pow(one)) % mod; return (int)res; } // Driver code static void Main(string[] args) { int[] arr = { 1, 2, 3, 4 }; int n = arr.Length; CheckPrimeVal(); // Function call Console.WriteLine(GoodSubsets(arr, n)); }} |
Javascript
const mod = 1000000007;const map_ = new Array(31).fill(0);// Function to calculate powerfunction pow(n) { let res = 1; let m = 2; while (n !== 0) { if ((n & 1) === 1) { res = (res * m) % mod; } m = (m * m) % mod; n >>= 1; } return res;}// Check for prime valuefunction check_prime_val() { const prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]; for (let i = 2; i <= 30; ++i) { // If num is a multiple of // 4/9/25, adding it to any // subset will make it bad if (i % 4 === 0 || i % 9 === 0 || i === 25) { continue; } let mask = 0; for (let j = 0; j < 10; ++j) { if (i % prime[j] === 0) { mask |= 1 << j; } } map_[i] = mask; }}function goodSubsets(arr, n) { let one = 0; // dp[set_of_primes] represents // the number of times set_of_primes // can be formed (set_of_primes === // mask) Since there are 10 possible // prime numbers, there are 2^10 // possible set_of_primes const dp = new Array(1024).fill(0); const cnt = new Array(31).fill(0); dp[0] = 1; for (let i = 0; i < n; i++) { if (arr[i] === 1) { one++; } else if (map_[arr[i]] !== 0) { cnt[arr[i]]++; } } for (let i = 0; i < 31; ++i) { if (cnt[i] === 0) { continue; } for (let j = 0; j < 1024; ++j) { if ((j & map_[i]) !== 0) { continue; } dp[j | map_[i]] = (dp[j | map_[i]] + dp[j] * cnt[i]) % mod; } } let res = 0; for (let i of dp) { res = (res + i) % mod; } res--; if (one !== 0) { res = (res * pow(one)) % mod; } return res;}// Driver codeconst arr = [1, 2, 3, 4];const n = arr.length;check_prime_val();console.log(goodSubsets(arr, n)); |
Output
6
Time Complexity: O(N*logN)
Auxiliary Space: O(N)
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!
