Problem

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

Examples

Example 1

1
2
3
4
5
6
7
8
9
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

1
2
3
4
5
6
7
8
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 <= 10^5
  • 1 <= nums[i] <= 30

Solution

Method 1 - Bitmask DP for Square-Free Products

We use bitmask dynamic programming to count subsets whose product is a product of distinct primes (i.e., square-free). We skip numbers with repeated prime factors. For each valid number, we update the DP for all compatible masks. The answer is multiplied by the number of 1’s in the input, as 1 can be included or not in any subset.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <vector>
using namespace std;
class Solution {
public:
    int numberOfGoodSubsets(vector<int>& nums) {
        const int MOD = 1e9+7;
        vector<int> primes = {2,3,5,7,11,13,17,19,23,29};
        vector<int> cnt(31);
        for (int x : nums) ++cnt[x];
        vector<int> mask(31);
        for (int i = 2; i <= 30; ++i) {
            int m = 0, x = i, ok = 1;
            for (int j = 0; j < primes.size(); ++j) {
                int p = primes[j], c = 0;
                while (x % p == 0) { x /= p; ++c; }
                if (c > 1) ok = 0;
                if (c) m |= 1 << j;
            }
            if (ok && x == 1) mask[i] = m;
        }
        vector<int> dp(1<<10);
        dp[0] = 1;
        for (int i = 2; i <= 30; ++i) {
            if (!mask[i] || !cnt[i]) continue;
            for (int s = (1<<10)-1; s >= 0; --s) {
                if ((s & mask[i]) == 0)
                    dp[s|mask[i]] = (dp[s|mask[i]] + (long long)dp[s] * cnt[i]) % MOD;
            }
        }
        long long res = 0, pow1 = 1;
        for (int s = 1; s < (1<<10); ++s) res = (res + dp[s]) % MOD;
        for (int i = 0; i < cnt[1]; ++i) pow1 = pow1 * 2 % MOD;
        return res * pow1 % MOD;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;
class Solution {
    public int numberOfGoodSubsets(int[] nums) {
        int MOD = 1_000_000_007;
        int[] primes = {2,3,5,7,11,13,17,19,23,29};
        int[] cnt = new int[31];
        for (int x : nums) cnt[x]++;
        int[] mask = new int[31];
        for (int i = 2; i <= 30; ++i) {
            int m = 0, x = i, ok = 1;
            for (int j = 0; j < primes.length; ++j) {
                int p = primes[j], c = 0;
                while (x % p == 0) { x /= p; ++c; }
                if (c > 1) ok = 0;
                if (c > 0) m |= 1 << j;
            }
            if (ok == 1 && x == 1) mask[i] = m;
        }
        int[] dp = new int[1<<10];
        dp[0] = 1;
        for (int i = 2; i <= 30; ++i) {
            if (mask[i] == 0 || cnt[i] == 0) continue;
            for (int s = (1<<10)-1; s >= 0; --s) {
                if ((s & mask[i]) == 0)
                    dp[s|mask[i]] = (int)((dp[s|mask[i]] + (long)(dp[s]) * cnt[i]) % MOD);
            }
        }
        long res = 0, pow1 = 1;
        for (int s = 1; s < (1<<10); ++s) res = (res + dp[s]) % MOD;
        for (int i = 0; i < cnt[1]; ++i) pow1 = pow1 * 2 % MOD;
        return (int)(res * pow1 % MOD);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
from typing import List
class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        primes = [2,3,5,7,11,13,17,19,23,29]
        cnt = [0]*31
        for x in nums:
            cnt[x] += 1
        mask = [0]*31
        for i in range(2, 31):
            m, x, ok = 0, i, True
            for j, p in enumerate(primes):
                c = 0
                while x % p == 0:
                    x //= p
                    c += 1
                if c > 1:
                    ok = False
                if c:
                    m |= 1 << j
            if ok and x == 1:
                mask[i] = m
        dp = [0] * (1<<10)
        dp[0] = 1
        for i in range(2, 31):
            if not mask[i] or not cnt[i]: continue
            for s in range((1<<10)-1, -1, -1):
                if (s & mask[i]) == 0:
                    dp[s|mask[i]] = (dp[s|mask[i]] + dp[s] * cnt[i]) % MOD
        res = sum(dp[1:]) % MOD
        pow1 = pow(2, cnt[1], MOD)
        return res * pow1 % MOD
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
impl Solution {
    pub fn number_of_good_subsets(nums: Vec<i32>) -> i32 {
        let primes = [2,3,5,7,11,13,17,19,23,29];
        let mut cnt = vec![0; 31];
        for &x in &nums { cnt[x as usize] += 1; }
        let mut mask = vec![0; 31];
        for i in 2..=30 {
            let mut m = 0;
            let mut x = i;
            let mut ok = true;
            for (j, &p) in primes.iter().enumerate() {
                let mut c = 0;
                while x % p == 0 {
                    x /= p;
                    c += 1;
                }
                if c > 1 { ok = false; }
                if c > 0 { m |= 1 << j; }
            }
            if ok && x == 1 { mask[i] = m; }
        }
        let mut dp = vec![0i64; 1<<10];
        dp[0] = 1;
        for i in 2..=30 {
            if mask[i] == 0 || cnt[i] == 0 { continue; }
            for s in (0..1<<10).rev() {
                if (s & mask[i]) == 0 {
                    dp[s|mask[i]] = (dp[s|mask[i]] + dp[s] * cnt[i] as i64) % 1_000_000_007;
                }
            }
        }
        let mut res = 0i64;
        for s in 1..(1<<10) { res = (res + dp[s]) % 1_000_000_007; }
        let mut pow1 = 1i64;
        for _ in 0..cnt[1] { pow1 = pow1 * 2 % 1_000_000_007; }
        (res * pow1 % 1_000_000_007) as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function numberOfGoodSubsets(nums: number[]): number {
    const MOD = 1e9+7;
    const primes = [2,3,5,7,11,13,17,19,23,29];
    const cnt = Array(31).fill(0);
    for (const x of nums) cnt[x]++;
    const mask = Array(31).fill(0);
    for (let i = 2; i <= 30; ++i) {
        let m = 0, x = i, ok = true;
        for (let j = 0; j < primes.length; ++j) {
            let p = primes[j], c = 0;
            while (x % p === 0) { x /= p; ++c; }
            if (c > 1) ok = false;
            if (c) m |= 1 << j;
        }
        if (ok && x === 1) mask[i] = m;
    }
    const dp = Array(1<<10).fill(0);
    dp[0] = 1;
    for (let i = 2; i <= 30; ++i) {
        if (!mask[i] || !cnt[i]) continue;
        for (let s = (1<<10)-1; s >= 0; --s) {
            if ((s & mask[i]) === 0)
                dp[s|mask[i]] = (dp[s|mask[i]] + dp[s] * cnt[i]) % MOD;
        }
    }
    let res = 0, pow1 = 1;
    for (let s = 1; s < (1<<10); ++s) res = (res + dp[s]) % MOD;
    for (let i = 0; i < cnt[1]; ++i) pow1 = pow1 * 2 % MOD;
    return res * pow1 % MOD;
}

Complexity

  • ⏰ Time complexity: O(N * 2^P) (N = input size, P = number of primes ≤ 30)
  • 🧺 Space complexity: O(2^P)