The Number of Good Subsets

Hard
1095.

The Number of Good Subsets

The Number of Good Subsets is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var numberOfGoodSubsets = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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

Hints for The Number of Good Subsets

  1. Hint 1

    Values above 30 never appear, so only the ten primes up to 29 matter — a 10-bit mask.

  2. Hint 2

    A value with a repeated prime factor (4, 8, 9, 12, …) can never be in a good subset.

  3. 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

  1. Tally the values and build, for each 2..30, its prime mask — or mark it unusable when a prime repeats.
  2. Run dp[mask] over the 1024 states, processing each usable value once and multiplying by how many copies it has.
  3. Sum dp[mask] over all non-zero masks.
  4. 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

Java

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