The Number of Good Subsets
HardPrompt
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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach explores all possibilities of forming subsets using recursion. We first process the input array to count the frequencies of each number and filter out numbers that cannot be in a good subset (i.e., numbers with a squared prime factor, like 4, 8, 9, ...). Then, we use a recursive function to build subsets from the valid, unique numbers. For each unique number, we decide whether to include it in our subset or not. The decision to include a number depends on whether its prime factors conflict with the prime factors of numbers already in the subset.
Algorithm
- Create a frequency map
freqfor numbers innums. - Identify square-free numbers from 2 to 30 and compute their prime factor bitmasks.
- Create a list
uniqueNumsof unique, square-free numbers > 1 present innums. - Define a recursive function
solve(index, mask)that calculates the number of ways to form good subsets using numbers fromuniqueNums[index:]given that the combined prime mask of the subset formed so far iscurrentMask. - The base case for the recursion is when
indexreaches the end ofuniqueNums, at which point it returns 1. - In the recursive step, for
num = uniqueNums[index], it computes the sum of two cases:- Skipping
num:solve(index + 1, mask). - Including
num(if its prime mask doesn't conflict):freq[num] * solve(index + 1, mask | prime_mask(num)).
- Skipping
- Call
solve(0, 0)to get the total number of valid subsets (including the empty one) from numbers > 1. Let the result betotal. - The number of non-empty good subsets from numbers > 1 is
(total - 1). - Calculate
p = 2^freq[1]using modular exponentiation. - The final answer is
((total - 1) * p) % MOD.
Walkthrough
First, we pre-calculate the prime factorization for each number from 2 to 30. We can represent the set of prime factors using a bitmask, as there are only 10 primes less than or equal to 30 (2, 3, 5, 7, 11, 13, 17, 19, 23, 29). We also filter out numbers that are not square-free (e.g., 4, 9, 12) because they can never be part of a good subset. We count the frequency of each number in nums. The count of 1s is handled separately. We create a list of unique, square-free numbers greater than 1 that appear in nums. A recursive function, say countGoodSubsets(index, currentMask), is defined. This function calculates the number of ways to form good subsets using numbers from unique_nums[index] onwards, given that the combined prime mask of the subset formed so far is currentMask. The initial call is countGoodSubsets(0, 0). This counts all subsets, including the empty one. We subtract 1 to exclude the empty set. Finally, we multiply this result by 2^countOfOnes to account for the subsets containing 1s. Each of the countOfOnes instances of 1 can either be in a subset or not, giving 2^countOfOnes possibilities for each good subset formed by other numbers.
// This is a conceptual sketch, not full implementation// It would be part of a larger class structureprivate int[] freq;private List<Integer> uniqueNums;private int[] primeMasks; // precomputedprivate long MOD = 1_000_000_007; private long solve(int index, int mask) { if (index == uniqueNums.size()) { return 1; // One way: choose empty set from here } // Option 1: Don't include uniqueNums[index] long count = solve(index + 1, mask); // Option 2: Include uniqueNums[index] int num = uniqueNums.get(index); int numMask = primeMasks[num]; if ((mask & numMask) == 0) { count = (count + (long)freq[num] * solve(index + 1, mask | numMask)) % MOD; } return count;}Complexity
Time
O(N + 2^U), where N is the length of `nums` and U is the number of unique, square-free numbers greater than 1 (U <= 29). The O(N) part is for counting frequencies. The O(2^U) part is for the recursion, which explores all combinations. This is too slow for the given constraints.
Space
O(U), where U is the number of unique, square-free numbers (U <= 29). This space is used for the recursion stack depth.
Trade-offs
Pros
Conceptually simple and a direct translation of the combinatorial problem.
Cons
Extremely inefficient due to re-computation of the same subproblems.
The number of recursive calls grows exponentially with the number of unique square-free numbers, leading to a "Time Limit Exceeded" error on most platforms.
This approach improves upon the brute-force backtracking by using memoization to store the results of subproblems that have already been solved. This avoids redundant computations and drastically reduces the time complexity. The state of a subproblem is defined by the current index in the list of unique numbers and the current prime factor mask. We use a 2D array, memo[index][mask], to store the result for solve(index, mask).
Algorithm
- Create a frequency map
freq. - Identify square-free numbers from 2 to 30, compute their prime masks, and add them to a list
uniqueNums. - Initialize a memoization table
memo[uniqueNums.size()][1024]with a sentinel value (e.g., -1). - Define a recursive function
solve(index, mask)that returns the number of valid subsets fromuniqueNums[index:]givenmask. It uses thememotable to store and retrieve results. - Before computing, the function checks
memo[index][mask]. If a value exists, it's returned. Otherwise, the result is computed recursively as in the brute-force approach. - The computed result is stored in
memo[index][mask]before returning. - Call
solve(0, 0)to get the total number of valid subsets (including empty). - Subtract 1 for the empty set.
- Multiply by
2^freq[1]for the subsets involving 1s. - Return the final result modulo 10^9 + 7.
Walkthrough
The overall logic is identical to the pure backtracking approach. We still count frequencies, filter numbers, and use a recursive function. The key difference is the addition of a memoization table, memo, initialized with a value indicating that the state has not been computed (e.g., -1). The recursive function solve(index, mask) is modified: at the beginning of the function, it checks if memo[index][mask] has been computed. If so, it returns the stored value immediately. If not, it computes the result as in the pure backtracking approach and stores it in memo[index][mask] before returning. This technique is also known as top-down dynamic programming. It transforms the exponential complexity of the naive recursion into a polynomial time complexity determined by the number of states.
class Solution { int[] freq; List<Integer> uniqueNums; int[] primeMasks; long[][] memo; long MOD = 1_000_000_007; int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; public int numberOfGoodSubsets(int[] nums) { freq = new int[31]; for (int num : nums) { freq[num]++; } primeMasks = new int[31]; uniqueNums = new ArrayList<>(); for (int i = 2; i <= 30; i++) { if (freq[i] == 0) continue; int mask = 0; int temp = i; boolean isSquareFree = true; for (int j = 0; j < 10; j++) { if (temp % primes[j] == 0) { if ((temp / primes[j]) % primes[j] == 0) { isSquareFree = false; break; } mask |= (1 << j); } } if (isSquareFree) { uniqueNums.add(i); primeMasks[i] = mask; } } memo = new long[uniqueNums.size()][1 << 10]; for (long[] row : memo) { Arrays.fill(row, -1); } long count = solve(0, 0); long result = (count - 1 + MOD) % MOD; // Exclude the empty set long onesMultiplier = 1; for (int i = 0; i < freq[1]; i++) { onesMultiplier = (onesMultiplier * 2) % MOD; } result = (result * onesMultiplier) % MOD; return (int) result; } private long solve(int index, int mask) { if (index == uniqueNums.size()) { return 1; } if (memo[index][mask] != -1) { return memo[index][mask]; } // Option 1: Don't include uniqueNums[index] long count = solve(index + 1, mask); // Option 2: Include uniqueNums[index] int num = uniqueNums.get(index); int numMask = primeMasks[num]; if ((mask & numMask) == 0) { count = (count + (long)freq[num] * solve(index + 1, mask | numMask)) % MOD; } return memo[index][mask] = count; }}Complexity
Time
O(N + U * 2^P), where N is `nums.length`, U is the number of unique square-free numbers > 1 (<= 29), and P is the number of primes <= 30 (10). Each state `(index, mask)` is computed once.
Space
O(U * 2^P) for the memoization table, plus O(U) for the recursion stack. This is effectively O(30 * 1024), which is constant space with respect to N.
Trade-offs
Pros
Efficient and guaranteed to pass within time limits.
Relatively easy to write once the recursive structure is defined.
Cons
Uses extra space for the memoization table.
Can lead to a
StackOverflowErrorfor very deep recursion, though not an issue here due to the small problem constraints (depth is at most 30).
This is the most efficient approach, implementing the same logic as the memoized recursion but in an iterative, bottom-up fashion. It avoids recursion overhead and can be slightly more space-efficient. We use a DP array, dp[mask], where dp[mask] stores the number of subsets whose product's prime factors are represented by mask. We iterate through each unique, valid number from the input and update the DP table accordingly.
Algorithm
- Create a frequency map
freq. - Initialize a DP array
dpof size 1024 withdp[0] = 1. - Iterate
numfrom 2 to 30. Iffreq[num] == 0, continue. - Check if
numis square-free. If not, continue. - Calculate the prime mask
numMaskfornum. - Iterate
maskfrom 1023 down to 0. - If
(mask & numMask) == 0, updatedp[mask | numMask] = (dp[mask | numMask] + dp[mask] * freq[num]) % MOD. - After iterating through all numbers, sum up
dp[mask]formaskfrom 1 to 1023. This is the count of good subsets from numbers > 1. - Multiply the result by
2^freq[1]using modular exponentiation. - Return the final result.
Walkthrough
The pre-processing steps are the same: count frequencies and identify valid numbers (square-free, > 1) and their prime masks. We initialize a DP array dp of size 1 << 10 (1024). dp[0] is set to 1, representing the single empty subset, and all other dp[i] are 0. We iterate through each unique, square-free number num > 1 that is present in nums. For each num, we iterate through all possible existing prime masks mask from (1 << 10) - 1 down to 0. If dp[mask] is non-zero and num's prime mask numMask does not conflict with mask (i.e., (mask & numMask) == 0), we can form new subsets by adding num. The number of new subsets formed is dp[mask] * freq[num]. These new subsets will have a combined prime mask of mask | numMask. So, we update dp[mask | numMask] by adding this amount. The iteration over mask must be done from high to low to avoid using a number num multiple times with subsets that were just formed in the current step. After iterating through all unique numbers, the dp array is fully populated. The total number of non-empty good subsets is the sum of all dp[mask] for mask > 0. Finally, this sum is multiplied by 2^freq[1] to account for the number 1.
class Solution { public int numberOfGoodSubsets(int[] nums) { int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; int MOD = 1_000_000_007; int[] freq = new int[31]; for (int n : nums) { freq[n]++; } long[] dp = new long[1 << 10]; dp[0] = 1; for (int i = 2; i <= 30; i++) { if (freq[i] == 0) continue; // Check if i is square-free and get its mask int mask = 0; int temp = i; boolean isSquareFree = true; for (int j = 0; j < 10; j++) { if (temp % primes[j] == 0) { if ((temp / primes[j]) % primes[j] == 0) { isSquareFree = false; break; } mask |= (1 << j); } } if (!isSquareFree) continue; // Update DP table for (int prevMask = (1 << 10) - 1; prevMask >= 0; prevMask--) { if (dp[prevMask] > 0 && (prevMask & mask) == 0) { int newMask = prevMask | mask; dp[newMask] = (dp[newMask] + dp[prevMask] * freq[i]) % MOD; } } } long totalGoodSubsets = 0; for (int i = 1; i < (1 << 10); i++) { totalGoodSubsets = (totalGoodSubsets + dp[i]) % MOD; } long onesMultiplier = 1; for (int i = 0; i < freq[1]; i++) { onesMultiplier = (onesMultiplier * 2) % MOD; } return (int)((totalGoodSubsets * onesMultiplier) % MOD); }}Complexity
Time
O(N + C * 2^P), where N is `nums.length`, C is the number range (30), and P is the number of primes (10). This is dominated by O(N) if N is large, making it very efficient.
Space
O(C + 2^P) for the frequency map and the DP table, where C is the number range (30) and P is the number of primes (10). This is constant space, O(1), with respect to N.
Trade-offs
Pros
Most efficient in terms of both time and space.
Avoids recursion, eliminating recursion overhead and risk of stack overflow.
The logic is clean and directly models the state transitions.
Cons
Can be slightly less intuitive to formulate than the recursive solution for some.
Solutions
Solution
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)1 e9 + 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)) % modVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.