The Number of Good Subsets solution and explanation
4 more videos on this problem
LeetCode 1994. The Number of Good SubsetsHappy Coding · 29:02 · 2K views
1994. The Number of Good Subsets (Leetcode Hard)Programming Live with Larry · 46:09 · 800 views
【每日一题】LeetCode 1994. The Number of Good Subsets, 9/9/2021Huifeng Guan · 46:43 · 666 views
Day 33/75: Problem Name: The Number of Good Subsets | Leetcode | #75DaysHardLeetcodeCodeInsanity · 10:27 · 545 views
LeetCode 1994: The Number of Good SubsetsAlitaCode · 33:51 · 11 views
The problem
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 = 3respectively.[1, 4]and[4]are not good subsets with products4 = 2*2and4 = 2*2respectively.
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
Approach overview
Problem Overview: You receive an array of integers where each value is between 1 and 30. A subset is considered good if the product of its elements can be represented as a multiplication of distinct prime numbers. The task is to count all such subsets modulo 1e9+7.
Approach 1: Bitmask Dynamic Programming (O(n + 30 * 2^10) time, O(2^10) space)
This approach relies on the fact that numbers from 1 to 30 only contain the first 10 primes: 2,3,5,7,11,13,17,19,23,29. Each number can be represented as a prime mask where each bit indicates whether a prime factor appears in its factorization. If a number contains a squared prime factor (like 4 = 2² or 12 = 2²×3), it cannot appear in a good subset and is ignored.
Build a frequency map of values in the array. Then run dynamic programming over masks where dp[mask] represents the number of ways to form a subset with that prime combination. For each valid number, compute its mask and update states by iterating existing masks and merging them if the prime sets do not overlap (mask & numMask == 0). The value 1 is handled separately since it contributes no primes; it multiplies the final result by 2^count(1). This method efficiently enumerates all valid prime combinations using bitmask states and dynamic programming.
Approach 2: Combinatorial Counting with Prime Masks (O(30 * 2^10) time, O(2^10) space)
This variation focuses on counting occurrences first and then performing transitions using combinatorics. Precompute the frequency of each number from 2 to 30. Convert every valid number into its prime mask and skip numbers containing repeated primes. Then iterate through numbers and update DP states similarly to subset DP: for every mask, add contributions from the current number multiplied by its frequency.
The difference from the previous approach is conceptual. Instead of iterating the original array, you iterate the compressed frequency list of numbers (only 30 possibilities). This reduces redundant work when the input array is large. The DP still ensures that no prime factor appears twice by checking mask overlap before combining states. This approach blends math factorization with mask-based subset construction.
Recommended for interviews: Bitmask dynamic programming is the expected solution. It shows you recognize the constraint that numbers are limited to 30, map prime factors to bits, and run subset-style DP over masks. Starting with the frequency observation and explaining why numbers with squared primes are invalid demonstrates strong reasoning. The optimal solution uses only 1024 DP states and handles the entire array efficiently.
Approach 1: Bitmask Dynamic Programming
This approach involves using dynamic programming with bitmask to track subsets of products using primes. Each number up to 30 can be represented by a bitmask for its prime factors. The state DP[mask] represents the count of good subsets with that specific prime factorization. We build this state for all numbers in the array.
def goodSubsets(nums):
MOD = 10**9 + 7
freq = [0] * 31
for num in nums:
freq[num] += 1
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
valid_masks = []
for i in range(2, 31):
mask = 0
is_square_free = True
for j, prime in enumerate(primes):
if i % (prime * prime) == 0:
is_square_free = False
break
if i % prime == 0:
mask |= (1 << j)
if is_square_free:
valid_masks.append((i, mask))
dp = [0] * (1 << len(primes))
dp[0] = 1
for num, mask in valid_masks:
if freq[num] == 0:
continue
for current_mask in range((1 << len(primes)) - 1, -1, -1):
if current_mask & mask == 0:
dp[current_mask | mask] = (dp[current_mask | mask] + dp[current_mask] * freq[num]) % MOD
result = sum(dp) - 1
result = (result * pow(2, freq[1], MOD)) % MOD
return result
# Example Usage:
print(goodSubsets([1,2,3,4])) # Output: 6
print(goodSubsets([4,2,3,15])) # Output: 5#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;
int goodSubsets(vector<int>& nums) {
vector<int> freq(31, 0);
for (int num : nums) {
freq[num]++;
}
vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
vector<pair<int, int>> valid_masks;
for (int i = 2; i <= 30; ++i) {
int mask = 0;
bool is_square_free = true;
for (int j = 0; j < primes.size(); ++j) {
if (i % (primes[j] * primes[j]) == 0) {
is_square_free = false;
break;
}
if (i % primes[j] == 0) {
mask |= (1 << j);
}
}
if (is_square_free) {
valid_masks.push_back({i, mask});
}
}
vector<int> dp(1 << primes.size(), 0);
dp[0] = 1;
for (auto [num, mask] : valid_masks) {
if (freq[num] == 0) continue;
for (int current_mask = (1 << primes.size()) - 1; current_mask >= 0; --current_mask) {
if ((current_mask & mask) == 0) {
dp[current_mask | mask] = (dp[current_mask | mask] + 1LL * dp[current_mask] * freq[num]) % MOD;
}
}
}
long long result = -1; // minus empty subset
for (int count : dp) {
result = (result + count) % MOD;
}
long long pow2_1s = 1;
for (int i = 0; i < freq[1]; i++) {
pow2_1s = (pow2_1s * 2) % MOD;
}
result = (result * pow2_1s) % MOD;
return result;
}
int main() {
vector<int> nums1 = {1, 2, 3, 4};
cout << goodSubsets(nums1) << endl; // Output: 6
vector<int> nums2 = {4, 2, 3, 15};
cout << goodSubsets(nums2) << endl; // Output: 5
}The Python solution initializes a frequency array for numbers 1 through 30. It collects valid subsets (where product is made of distinct primes) using bitmasks to represent which primes are included. The solution uses dynamic programming states to calculate possible subsets and finally scales the result for any number of 1's in the original list.
Time Complexity: O(30 * 2^10) due to iterating over primes using bitmask expansion
Space Complexity: O(2^10) which is the size of the DP array.
Approach 2: Combinatorial Counting with Prime Masks
Another efficient method involves constructing a dynamic programming solution by enumerating possible combinations of unique primes using subset masks. This method also incorporates combinatorial counting principles aligned with the bitmask patterns to include numbers from input.
We first identify prime numbers up to 30 which are products consisting only of unique primes can exist and then we calculate subsets fulfilling these criteria through optimal dynamic counting.
import java.util.*;
public class GoodSubsets {
private static final int MOD = 1000000007;
public int goodSubsets(int[] nums) {
int[] freq = new int[31];
Arrays.fill(freq, 0);
for (int num : nums) {
freq[num]++;
}
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
List<int[]> validMasks = new ArrayList<>();
for (int i = 2; i <= 30; i++) {
int mask = 0;
boolean isSquareFree = true;
for (int j = 0; j < primes.length; j++) {
if (i % (primes[j] * primes[j]) == 0) {
isSquareFree = false;
break;
}
if (i % primes[j] == 0) {
mask |= (1 << j);
}
}
if (isSquareFree) {
validMasks.add(new int[]{i, mask});
}
}
int[] dp = new int[1 << primes.length];
dp[0] = 1;
for (int[] pair : validMasks) {
int num = pair[0], numMask = pair[1];
if (freq[num] == 0) continue;
for (int i = (1 << primes.length) - 1; i >= 0; --i) {
if ((i & numMask) == 0) {
dp[i | numMask] = (int)((dp[i | numMask] + (long)dp[i] * freq[num]) % MOD);
}
}
}
long result = 0;
for (int count : dp) {
result = (result + count) % MOD;
}
result = (result - 1 + MOD) % MOD;
long pow2_1s = 1;
for (int i = 0; i < freq[1]; i++) {
pow2_1s = (pow2_1s * 2) % MOD;
}
return (int)((result * pow2_1s) % MOD);
}
public static void main(String[] args) {
GoodSubsets solution = new GoodSubsets();
System.out.println(solution.goodSubsets(new int[]{1, 2, 3, 4}));
System.out.println(solution.goodSubsets(new int[]{4, 2, 3, 15}));
}
}const goodSubsets = (nums) => {
const MOD = 1000000007;
const freq = Array(31).fill(0);
nums.forEach(num => freq[num]++);
const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
const validMasks = [];
for (let i = 2; i <= 30; i++) {
let mask = 0;
let isSquareFree = true;
for (let j = 0; j < primes.length; j++) {
if (i % (primes[j] ** 2) === 0) {
isSquareFree = false;
break;
}
if (i % primes[j] === 0) {
mask |= (1 << j);
}
}
if (isSquareFree) {
validMasks.push([i, mask]);
}
}
const dp = Array(1 << primes.length).fill(0);
dp[0] = 1;
validMasks.forEach(([num, mask]) => {
if (freq[num] === 0) return;
for (let currentMask = (1 << primes.length) - 1; currentMask >= 0; currentMask--) {
if ((currentMask & mask) === 0) {
dp[currentMask | mask] = (dp[currentMask | mask] + dp[currentMask] * freq[num]) % MOD;
}
}
});
let result = dp.reduce((sum, value) => (sum + value) % MOD, 0) - 1;
const pow2_1s = Array(freq[1]).fill(0).reduce(p => (p * 2) % MOD, 1);
return (result * pow2_1s) % MOD;
};
// Example Usage:
console.log(goodSubsets([1, 2, 3, 4])); // Output: 6
console.log(goodSubsets([4, 2, 3, 15])); // Output: 5;The Java solution utilizes combinatorial logic in conjunction with prime masks. It develops a set approach to track subset validity, dynamically calculates options, and gives relevant outputs according to set conditions among given number constraints. Long values achieve modular arithmetic results effectively.
Time Complexity: O(30 * 2^10)
Space Complexity: O(2^10)
Approach 3: Default Approach
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
}Complexity comparison
| Approach | Complexity |
|---|---|
| Bitmask Dynamic Programming | Time Complexity: O(30 * 2^10) due to iterating over primes using bitmask expansion |
| Combinatorial Counting with Prime Masks | Time Complexity: O(30 * 2^10) |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitmask Dynamic Programming | O(n + 30 * 2^10) | O(2^10) | General optimal solution when numbers are limited to 1–30 and prime masks can represent factor sets |
| Combinatorial Counting with Prime Masks | O(30 * 2^10) | O(2^10) | When using frequency compression to avoid iterating the entire array repeatedly |
Frequently asked questions
Is The Number of Good Subsets easy or hard?
LeetCode classifies this problem as Hard. The difficulty comes from recognizing the constraint that numbers are limited to 30, mapping prime factors to bitmasks, filtering numbers with repeated primes, and performing subset DP efficiently.
The Number of Good Subsets Python/Java solution
Most implementations compute a prime mask for each number, maintain a DP array of size 1024, and update states while ensuring masks do not overlap. The same logic translates easily across Python, Java, C++, and JavaScript since it relies on simple bit operations and modular arithmetic.
How to solve The Number of Good Subsets in O(n)?
A near-linear solution uses frequency counting combined with bitmask DP. First count occurrences of each value, then process the limited range of numbers (2–30) instead of the entire array repeatedly. The DP over 1024 masks keeps the effective complexity close to O(n).
What is the best approach for The Number of Good Subsets?
Bitmask dynamic programming is the most effective approach. Each number is mapped to a bitmask representing its prime factors among the first 10 primes. A DP array of size 2^10 tracks valid prime combinations while ensuring no prime appears more than once. The overall complexity is about O(n + 30 * 1024).
Is The Number of Good Subsets asked at Google/Amazon/Meta?
Problems involving bitmask dynamic programming and prime factor masks frequently appear in interviews at companies like Google, Amazon, and Meta. This problem tests number theory insight, subset DP, and bit manipulation techniques often expected in senior-level coding interviews.
What data structure is used in The Number of Good Subsets?
The core structure is a DP array indexed by bitmasks representing sets of prime factors. A frequency map or counting array for values 1–30 is also used to compress the input and speed up transitions.
What is the time complexity of The Number of Good Subsets?
The optimal solution runs in O(n + 30 * 2^10) time. The array is scanned once to compute frequencies, and dynamic programming iterates over at most 30 possible values and 1024 mask states. Space complexity is O(2^10) for the DP table.