README_EN.md

1994. The Number of Good Subsets

中文文档

Description

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

Solutions

Python3

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        counter = Counter(nums)
        mod = 10**9 + 7
        prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        n = len(prime)
        dp = [0] * (1 << n)
        dp[0] = 1
        for x in range(2, 31):
            if counter[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0:
                continue
            mask = 0
            for i, p in enumerate(prime):
                if x % p == 0:
                    mask |= (1 << i)
            for state in range(1 << n):
                if mask & state:
                    continue
                dp[mask | state] = (dp[mask | state] + counter[x] * dp[state]) % mod
        ans = 0
        for i in range(1, 1 << n):
            ans = (ans + dp[i]) % mod
        for i in range(counter[1]):
            ans = (ans << 1) % mod
        return ans

Java

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int numberOfGoodSubsets(int[] nums) {
        int[] counter = new int[31];
        for (int x : nums) {
            ++counter[x];
        }
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        int n = prime.length;
        long[] dp = new long[1 << n];
        dp[0] = 1;
        for (int x = 2; x <= 30; ++x) {
            if (counter[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
                continue;
            }
            int mask = 0;
            for (int i = 0; i < n; ++i) {
                if (x % prime[i] == 0) {
                    mask |= (1 << i);
                }
            }
            for (int state = 0; state < 1 << n; ++state) {
                if ((mask & state) > 0) {
                    continue;
                }
                dp[mask | state] = (dp[mask | state] + counter[x] * dp[state]) % MOD;
            }
        }
        long ans = 0;
        for (int i = 1; i < 1 << n; ++i) {
            ans = (ans + dp[i]) % MOD;
        }
        while (counter[1]-- > 0) {
            ans = (ans << 1) % MOD;
        }
        return (int) ans;
    }
}

C++

class Solution {
public:
    int numberOfGoodSubsets(vector<int>& nums) {
        vector<int> counter(31);
        for (int& x : nums) ++counter[x];
        vector<int> prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        const int MOD = 1e9 + 7;
        int n = prime.size();
        vector<long long> dp(1 << n);
        dp[0] = 1;
        for (int x = 2; x <= 30; ++x)
        {
            if (counter[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) continue;
            int mask = 0;
            for (int i = 0; i < n; ++i)
                if (x % prime[i] == 0)
                    mask |= (1 << i);
            for (int state = 0; state < 1 << n; ++state)
            {
                if ((mask & state) > 0) continue;
                dp[mask | state] = (dp[mask | state] + counter[x] * dp[state]) % MOD;
            }
        }
        long long ans = 0;
        for (int i = 1; i < 1 << n; ++i) ans = (ans + dp[i]) % MOD;
        while (counter[1]--) ans = (ans << 1) % MOD;
        return (int) ans;
    }
};

Go

func numberOfGoodSubsets(nums []int) int {
	counter := make([]int, 31)
	for _, x := range nums {
		counter[x]++
	}
	const mod int = 1e9 + 7
	prime := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
	n := len(prime)
	dp := make([]int, 1<<n)
	dp[0] = 1
	for x := 2; x <= 30; x++ {
		if counter[x] == 0 || x%4 == 0 || x%9 == 0 || x%25 == 0 {
			continue
		}
		mask := 0
		for i, p := range prime {
			if x%p == 0 {
				mask |= (1 << i)
			}
		}
		for state := 0; state < 1<<n; state++ {
			if (mask & state) > 0 {
				continue
			}
			dp[mask|state] = (dp[mask|state] + counter[x]*dp[state]) % mod
		}
	}
	ans := 0
	for i := 1; i < 1<<n; i++ {
		ans = (ans + dp[i]) % mod
	}
	for counter[1] > 0 {
		ans = (ans << 1) % mod
		counter[1]--
	}
	return ans
}

...