Skip to main content
Talentd

The Number of Good Subsets - Solution & Explanation

HardArrayMathDynamic ProgrammingBit Manipulation12 min readAsked at: Lowe, Medianet
Practice this problem

Problem Statement

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.

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 <= 105
  • 1 <= 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.

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.

Code

PythonC++

Python

C++

Complexity

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.

Try this approach in the editor →

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.

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.

Code

JavaJavaScript

Java

JavaScript

Complexity

Time Complexity: O(30 * 2^10)
Space Complexity: O(2^10)

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Bitmask Dynamic Programming

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.

Combinatorial Counting with Prime Masks

Time Complexity: O(30 * 2^10)
Space Complexity: O(2^10)

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bitmask Dynamic ProgrammingO(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 MasksO(30 * 2^10)O(2^10)When using frequency compression to avoid iterating the entire array repeatedly

Video Solution

LeetCode 1994. The Number of Good Subsets • Happy Coding • 2,611 views views

Watch 4 more video solutions →

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.

Ready to solve this problem?

Practice The Number of Good Subsets with our built-in code editor and test cases.

Practice on FleetCode
Previous

Fair Distribution of Cookies

Next

Number of Ways to Wear Different Hats to Each Other