#1994
The Number of Good Subsets
master · 1785 · lc hard +32 · verified · 37.1% accepted · 507 likes · top 15%
Description
Given an integer array nums, a subset is called good if its product equals a product of one or more distinct primes.
For instance, with nums = [1, 2, 3, 4]: subsets [2, 3], [1, 2, 3], and [1, 3] are good (products 6, 6, 3), while [1, 4] and [4] are not (product 4 = 2*2 has a repeated prime factor).
Count all good subsets of nums modulo 109 + 7. Two subsets differ when the sets of chosen indices differ.
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.
Code
1
2
3