The Number of Good Subsets — Hard Problem & Solution

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…

Difficulty: Hard
Topics: Arrays, Math, Dynamic Programming, 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^5
1 <= nums[i] <= 30

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) % MOD

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue