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.
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.
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] <= 30Problem 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.
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.
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.
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.
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.
Java
JavaScript
Time Complexity: O(30 * 2^10)
Space Complexity: O(2^10)
| 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 | — |
| 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 |
LeetCode 1994. The Number of Good Subsets • Happy Coding • 2,572 views views
Watch 6 more video solutions →Practice The Number of Good Subsets with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor