Welcome to Subscribe On Youtube
1994. The Number of Good Subsets
Description
You are given an integer array nums
. We call a subset of nums
good if its product can be represented as a product of one or more distinct prime numbers.
 For example, if
nums = [1, 2, 3, 4]
:[2, 3]
,[1, 2, 3]
, and[1, 3]
are good subsets with products6 = 2*3
,6 = 2*3
, and3 = 3
respectively.[1, 4]
and[4]
are not good subsets with products4 = 2*2
and4 = 2*2
respectively.
Return the number of different good subsets in nums
modulo 10^{9} + 7
.
A subset of nums
is any array that can be obtained by deleting some (possibly none or all) elements from nums
. Two subsets are different if and only if the chosen indices to delete are different.
Example 1:
Input: nums = [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.
Example 2:
Input: nums = [4,2,3,15] Output: 5 Explanation: The good subsets are:  [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.  [2,15]: product is 30, which is the product of distinct primes 2, 3, and 5.  [3]: product is 3, which is the product of distinct prime 3.  [15]: product is 15, which is the product of distinct primes 3 and 5.
Constraints:
1 <= nums.length <= 10^{5}
1 <= nums[i] <= 30
Solutions

class Solution { public int numberOfGoodSubsets(int[] nums) { int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; int[] cnt = new int[31]; for (int x : nums) { ++cnt[x]; } final int mod = (int) 1e9 + 7; int n = primes.length; long[] f = new long[1 << n]; f[0] = 1; for (int i = 0; i < cnt[1]; ++i) { f[0] = (f[0] * 2) % mod; } for (int x = 2; x < 31; ++x) { if (cnt[x] == 0  x % 4 == 0  x % 9 == 0  x % 25 == 0) { continue; } int mask = 0; for (int i = 0; i < n; ++i) { if (x % primes[i] == 0) { mask = 1 << i; } } for (int state = (1 << n)  1; state > 0; state) { if ((state & mask) == mask) { f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod; } } } long ans = 0; for (int i = 1; i < 1 << n; ++i) { ans = (ans + f[i]) % mod; } return (int) ans; } }

class Solution { public: int numberOfGoodSubsets(vector<int>& nums) { int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; int cnt[31]{}; for (int& x : nums) { ++cnt[x]; } int n = 10; const int mod = 1e9 + 7; vector<long long> f(1 << n); f[0] = 1; for (int i = 0; i < cnt[1]; ++i) { f[0] = f[0] * 2 % mod; } for (int x = 2; x < 31; ++x) { if (cnt[x] == 0  x % 4 == 0  x % 9 == 0  x % 25 == 0) { continue; } int mask = 0; for (int i = 0; i < n; ++i) { if (x % primes[i] == 0) { mask = 1 << i; } } for (int state = (1 << n)  1; state; state) { if ((state & mask) == mask) { f[state] = (f[state] + 1LL * cnt[x] * f[state ^ mask]) % mod; } } } long long ans = 0; for (int i = 1; i < 1 << n; ++i) { ans = (ans + f[i]) % mod; } return ans; } };

class Solution: def numberOfGoodSubsets(self, nums: List[int]) > int: primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] cnt = Counter(nums) mod = 10**9 + 7 n = len(primes) f = [0] * (1 << n) f[0] = pow(2, cnt[1]) for x in range(2, 31): if cnt[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0: continue mask = 0 for i, p in enumerate(primes): if x % p == 0: mask = 1 << i for state in range((1 << n)  1, 0, 1): if state & mask == mask: f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod return sum(f[i] for i in range(1, 1 << n)) % mod

func numberOfGoodSubsets(nums []int) (ans int) { primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29} cnt := [31]int{} for _, x := range nums { cnt[x]++ } const mod int = 1e9 + 7 n := 10 f := make([]int, 1<<n) f[0] = 1 for i := 0; i < cnt[1]; i++ { f[0] = f[0] * 2 % mod } for x := 2; x < 31; x++ { if cnt[x] == 0  x%4 == 0  x%9 == 0  x%25 == 0 { continue } mask := 0 for i, p := range primes { if x%p == 0 { mask = 1 << i } } for state := 1<<n  1; state > 0; state { if state&mask == mask { f[state] = (f[state] + f[state^mask]*cnt[x]) % mod } } } for i := 1; i < 1<<n; i++ { ans = (ans + f[i]) % mod } return }