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]:<ul> <li><code>[2, 3]</code>, <code>[1, 2, 3]</code>, and <code>[1, 3]</code> are <strong>good</strong> subsets with products <code>6 = 2*3</code>, <code>6 = 2*3</code>, and <code>3 = 3</code> respectively.</li> <li><code>[1, 4]</code> and <code>[4]</code> are not <strong>good</strong> subsets with products <code>4 = 2*2</code> and <code>4 = 2*2</code> respectively.</li> </ul> </li>
Return the number of different good subsets in nums modulo 109 + 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 <= 1051 <= nums[i] <= 30
Companies:
Lowe
Related Topics:
Array, Math, Dynamic Programming, Bit Manipulation, Bitmask
Similar Questions:
// OJ: https://leetcode.com/problems/the-number-of-good-subsets/
// Author: github.com/lzl124631x
// Time: O(30 * 2^10)
// Space: O(2^10)
constexpr long mod = 1000000007;
int mask[31] = { -1, 0, 1, 2, -1, 4, 3, 8, -1, -1, 5, 16, -1, 32, 9, 6, -1, 64, -1, 128, -1, 10, 17, 256, -1, -1, 33, -1, -1, 512, 7 };
class Solution {
public:
int numberOfGoodSubsets(vector<int>& A) {
long dp[1025] = { 1 }, cnt[31] = {};
for (int n : A) ++cnt[n];
for (int i = 2; i <= 30; ++i) {
if (mask[i] == -1 || cnt[i] == 0) continue;
for (int mi = mask[i], mj = 0; mj < 1024; ++mj) {
dp[mi | mj] = (dp[mi | mj] + cnt[i] * dp[mj] * ((mi & mj) == 0)) % mod;
}
}
int ans = accumulate(begin(dp) + 1, end(dp), 0, [](int s, int n) { return (s + n) % mod; });
while (cnt[1]--) ans = (ans << 1) % mod;
return ans;
}
};Or
// OJ: https://leetcode.com/problems/the-number-of-good-subsets/
// Author: github.com/lzl124631x
// Time: O(30 * 2^10)
// Space: O(30 * 2^10)
long mod = 1e9 + 7, dp[1024][31] = {};
class Solution {
public:
int numberOfGoodSubsets(vector<int>& A) {
int primes[10] = {2,3,5,7,11,13,17,19,23,29}, cnt[31] = {}, bitmasks[31] = {}, bad[31] = {};
for (int n : A) cnt[n]++;
for (int i = 2; i <= 30; ++i) {
for (int j = 0; j < 10; ++j) {
if (i % primes[j] == 0) bitmasks[i] |= 1 << j;
}
}
for (int n : {4,8,9,12,16,18,20,24,25,27,28}) bad[n] = 1;
memset(dp, -1, sizeof(dp));
function<long(int, int)> dfs = [&](int mask, int num) -> long {
if (num == 1) return 1;
if (dp[mask][num] != -1) return dp[mask][num];
long ans = dfs(mask, num - 1); // If we skip this number
if (bad[num] == 0 && (mask & bitmasks[num]) == 0) { // If this number is not bad and it doesn't conflict with the selected numbers
ans = (ans + dfs(mask | bitmasks[num], num - 1) * cnt[num] % mod) % mod; // then we take this number
}
return dp[mask][num] = ans;
};
long ans = (dfs(0, 30) - 1 + mod) % mod;
while (cnt[1]--) ans = (ans << 1) % mod;
return ans;
}
};