The Number of Good Subsets — Solution in Python, Java & C++
The Number of Good Subsets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
The Number of Good Subsets is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Math, Bit Manipulation, Bitmask
- Asked at: Amazon, Google, Meta
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A subset of nums is good if it is non-empty and the product of its elements can be written as a product of distinct primes — that is, the product is square-free.
Return the number of good subsets, modulo 10⁹ + 7. Two subsets differ if they use different indices, even when the values match.
Example 1
Input: nums = [1,2,3,4]
Output: 6
Explanation: `{1}` is not good, but `{2}`, `{3}`, `{2,3}` each combine with including or excluding the 1.
Example 2
Input: nums = [4,2,3,15]
Output: 5
Explanation: `{2}`, `{3}`, `{15}`, `{2,3}` and `{2,15}`.
Example 3
Input: nums = [4,8,9]
Output: 0
Explanation: Every value has a squared prime factor.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 30
Hints for The Number of Good Subsets
Hint 1
Values above 30 never appear, so only the ten primes up to 29 matter — a 10-bit mask.
Hint 2
A value with a repeated prime factor (4, 8, 9, 12, …) can never be in a good subset.
Hint 3
1 multiplies the product by nothing, so each 1 can be included or not: multiply the answer by 2 per 1.
How to solve The Number of Good Subsets
Only values 1 to 30 appear, so each usable value maps to a 10-bit mask of its distinct primes; values with a squared factor are unusable. A subset-sum DP over those masks counts the good subsets among values 2 to 30, and the count of 1s contributes an independent factor of 2 each.
Approach
- Tally the values and build, for each 2..30, its prime mask — or mark it unusable when a prime repeats.
- Run
dp[mask]over the 1024 states, processing each usable value once and multiplying by how many copies it has. - Sum
dp[mask]over all non-zero masks. - Multiply by
2^(count of 1s).
Why it works
Multiplying by count[v] rather than looping over copies is what makes duplicates cheap: any one of the count[v] indices holding v gives a distinct subset, and since a good subset uses each value at most once, the copies never interact. The 1s factor out entirely because they change neither the product's primes nor the mask.
Complexity
- Time —
O(30 · 2¹⁰ + n) - Space —
O(2¹⁰)
Pitfalls
- The all-ones subset is not good — the empty prime mask is excluded from the sum.
- Values like 4, 8, 9, 12, 16, 18, 20, 24, 25, 27 and 28 have a squared prime and are unusable.
- Subsets are counted by index, so duplicate values multiply the count.
Reference solution
Python
from collections import Counter
from typing import List
def numberOfGoodSubsets(nums: List[int]) -> int:
MOD = 10**9 + 7
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
count = Counter(nums)
mask_of = {}
for v in range(2, 31):
m, t, ok = 0, v, True
for i, p in enumerate(primes):
if t % p == 0:
t //= p
if t % p == 0:
ok = False
break
m |= 1 << i
if ok and t == 1:
mask_of[v] = m
dp = [0] * 1024
dp[0] = 1
for v in range(2, 31):
if count[v] == 0 or v not in mask_of:
continue
m = mask_of[v]
for state in range(1023, -1, -1):
if state & m or dp[state] == 0:
continue
dp[state | m] = (dp[state | m] + dp[state] * count[v]) % MOD
total = sum(dp[1:]) % MOD
return total * pow(2, count[1], MOD) % MODJava
public static int numberOfGoodSubsets(int[] nums) {
final long MOD = 1000000007L;
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int[] count = new int[31];
for (int v : nums) count[v]++;
int[] maskOf = new int[31];
Arrays.fill(maskOf, -1);
for (int v = 2; v <= 30; v++) {
int m = 0, t = v;
boolean ok = true;
for (int p = 0; p < primes.length; p++) {
if (t % primes[p] == 0) {
t /= primes[p];
if (t % primes[p] == 0) {
ok = false;
break;
}
m |= 1 << p;
}
}
if (ok && t == 1) maskOf[v] = m;
}
long[] dp = new long[1024];
dp[0] = 1;
for (int v = 2; v <= 30; v++) {
if (count[v] == 0 || maskOf[v] < 0) continue;
int mv = maskOf[v];
for (int state = 1023; state >= 0; state--) {
if ((state & mv) != 0 || dp[state] == 0) continue;
dp[state | mv] = (dp[state | mv] + dp[state] * count[v]) % MOD;
}
}
long total = 0;
for (int state = 1; state < 1024; state++) total = (total + dp[state]) % MOD;
for (int i = 0; i < count[1]; i++) total = total * 2 % MOD;
return (int) total;
}C++
int numberOfGoodSubsets(vector<int>& nums) {
const long long MOD = 1000000007LL;
int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
vector<int> count(31, 0);
for (int v : nums) count[v]++;
vector<int> maskOf(31, -1);
for (int v = 2; v <= 30; v++) {
int m = 0, t = v;
bool ok = true;
for (int p = 0; p < 10; p++) {
if (t % primes[p] == 0) {
t /= primes[p];
if (t % primes[p] == 0) {
ok = false;
break;
}
m |= 1 << p;
}
}
if (ok && t == 1) maskOf[v] = m;
}
vector<long long> dp(1024, 0);
dp[0] = 1;
for (int v = 2; v <= 30; v++) {
if (count[v] == 0 || maskOf[v] < 0) continue;
int mv = maskOf[v];
for (int state = 1023; state >= 0; state--) {
if ((state & mv) != 0 || dp[state] == 0) continue;
dp[state | mv] = (dp[state | mv] + dp[state] * count[v]) % MOD;
}
}
long long total = 0;
for (int state = 1; state < 1024; state++) total = (total + dp[state]) % MOD;
for (int i = 0; i < count[1]; i++) total = total * 2 % MOD;
return (int) total;
}JavaScript
var numberOfGoodSubsets = function(nums) {
var MOD = 1000000007;
var PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
var mulmod = function(a, b) {
var hi = Math.floor(a / 65536), lo = a % 65536;
return ((hi * b % MOD) * 65536 + lo * b) % MOD;
};
var count = [], v, i;
for (v = 0; v <= 30; v++) count.push(0);
for (i = 0; i < nums.length; i++) count[nums[i]]++;
var maskOf = [];
for (v = 0; v <= 30; v++) maskOf.push(-1);
for (v = 2; v <= 30; v++) {
var m = 0, t = v, ok = true;
for (var p = 0; p < PRIMES.length; p++) {
if (t % PRIMES[p] === 0) {
t = t / PRIMES[p];
if (t % PRIMES[p] === 0) { ok = false; break; }
m |= 1 << p;
}
}
if (ok && t === 1) maskOf[v] = m;
}
var dp = [];
for (i = 0; i < 1024; i++) dp.push(0);
dp[0] = 1;
for (v = 2; v <= 30; v++) {
if (count[v] === 0 || maskOf[v] < 0) continue;
var mv = maskOf[v];
for (var state = 1023; state >= 0; state--) {
if ((state & mv) !== 0 || dp[state] === 0) continue;
dp[state | mv] = (dp[state | mv] + mulmod(dp[state], count[v])) % MOD;
}
}
var total = 0;
for (state = 1; state < 1024; state++) total = (total + dp[state]) % MOD;
for (i = 0; i < count[1]; i++) total = (total * 2) % MOD;
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Dynamic Programming