1994. The Number of Good Subsets LeetCode Solution
In this guide, you will get 1994. The Number of Good Subsets LeetCode Solution with the best time and space complexity. The solution to The Number of Good Subsets problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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 products 6 = 2*3, 6 = 2*3, and 3 = 3 respectively.
[1, 4] and [4] are not good subsets with products 4 = 2*2 and 4 = 2*2 respectively.
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.
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 <= 105
1 <= nums[i] <= 30
Complexity Analysis
Time Complexity: O(\max(\texttt{nums}) \cdot 2^{10})
Space Complexity: O(\max(\texttt{nums}) + 2^{10})
1994. The Number of Good Subsets LeetCode Solution in C++
class Solution {
public:
int numberOfGoodSubsets(vector<int>& nums) {
const vector<int> primes{2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
const int n = 1 << primes.size();
const int maxNum = ranges::max(nums);
vector<long> dp(n);
vector<int> count(maxNum + 1);
dp[0] = 1;
for (const int num : nums)
++count[num];
for (int num = 2; num <= maxNum; ++num) {
if (count[num] == 0)
continue;
if (num % 4 == 0 || num % 9 == 0 || num % 25 == 0)
continue;
const int numPrimesMask = getPrimesMask(num, primes);
for (int primesMask = 0; primesMask < n; ++primesMask) {
if ((primesMask & numPrimesMask) > 0)
continue;
const int nextPrimesMask = primesMask | numPrimesMask;
dp[nextPrimesMask] += dp[primesMask] * count[num];
dp[nextPrimesMask] %= kMod;
}
}
return modPow(2, count[1]) *
(accumulate(dp.begin() + 1, dp.end(), 0L) % kMod) % kMod;
}
private:
static constexpr int kMod = 1'000'000'007;
int getPrimesMask(int num, const vector<int>& primes) {
int primesMask = 0;
for (int i = 0; i < primes.size(); ++i)
if (num % primes[i] == 0)
primesMask |= 1 << i;
return primesMask;
}
long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x % kMod, (n - 1)) % kMod;
return modPow(x * x % kMod, (n / 2)) % kMod;
}
}; /* code provided by PROGIEZ */
1994. The Number of Good Subsets LeetCode Solution in Java
class Solution {
public int numberOfGoodSubsets(int[] nums) {
final int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
final int n = 1 << primes.length;
final int maxNum = Arrays.stream(nums).max().getAsInt();
long[] dp = new long[n];
int[] count = new int[maxNum + 1];
dp[0] = 1;
for (final int num : nums)
++count[num];
for (int num = 2; num <= maxNum; ++num) {
if (count[num] == 0)
continue;
if (num % 4 == 0 || num % 9 == 0 || num % 25 == 0)
continue;
final int numPrimesMask = getPrimesMask(num, primes);
for (int primesMask = 0; primesMask < n; ++primesMask) {
if ((primesMask & numPrimesMask) > 0)
continue;
final int nextPrimesMask = primesMask | numPrimesMask;
dp[nextPrimesMask] += dp[primesMask] * count[num];
dp[nextPrimesMask] %= kMod;
}
}
return (int) (modPow(2, count[1]) * ((Arrays.stream(dp).sum() - 1) % kMod) % kMod);
}
private static final int kMod = 1_000_000_007;
private int getPrimesMask(int num, int[] primes) {
int primesMask = 0;
for (int i = 0; i < primes.length; ++i)
if (num % primes[i] == 0)
primesMask |= 1 << i;
return primesMask;
}
private long modPow(long x, long n) {
if (n == 0)
return 1;
if (n % 2 == 1)
return x * modPow(x, n - 1) % kMod;
return modPow(x * x % kMod, n / 2);
}
} // code provided by PROGIEZ
1994. The Number of Good Subsets LeetCode Solution in Python
class Solution:
def numberOfGoodSubsets(self, nums: list[int]) -> int:
kMod = 1_000_000_007
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
n = 1 << len(primes)
# dp[i] := the number of good subsets with set of primes = i bit mask
dp = [1] + [0] * (n - 1)
count = collections.Counter(nums)
for num, freq in count.items():
if num == 1:
continue
if any(num % squared == 0 for squared in [4, 9, 25]):
continue
numPrimesMask = sum(1 << i
for i, prime in enumerate(primes)
if num % prime == 0)
for primesMask in range(n):
# Skip since there're commen set of primes (becomes invalid subset)
if primesMask & numPrimesMask > 0:
continue
nextPrimesMask = numPrimesMask | primesMask
dp[nextPrimesMask] += dp[primesMask] * freq
dp[nextPrimesMask] %= kMod
return (1 << count[1]) * sum(dp[1:]) % kMod # code by PROGIEZ
