#1994

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

The Number of Good Subsets

Find the number of good subsets in an integer array, where each subset's product is the product of distinct primes.

array hash table math dynamic programming bit manipulation

Problem Statement

You are given an integer array nums. A subset of nums is considered good if the product of its elements can be expressed as the product of distinct prime numbers. You need to count the number of such good subsets of nums and return the result modulo $10^9 + 7$ .

A subset of nums is any combination that can be obtained by removing some (possibly none or all) elements. Subsets are considered distinct based on the indices of the removed elements. Your task is to return the total number of good subsets.

Examples

Example 1

Input: nums = [1,2,3,4]

Output: 6

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

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

Solution Approach

Prime Factorization and Masking

The solution revolves around prime factorization and bit manipulation. We factorize each number in nums into primes and use bitmasking to track which primes have been used. This approach efficiently identifies good subsets based on distinct prime products.

Dynamic Programming with Hash Map

A dynamic programming approach is used with a hash map to store and update the number of subsets with each unique prime factorization. The hash map enables quick lookups and updates, significantly reducing the time complexity compared to brute force methods.

Modulo Arithmetic for Large Numbers

Since the number of good subsets can be large, the result is calculated modulo $10^9 + 7$ . This ensures that the solution can handle large inputs without overflowing and meets the problem's constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on the approach. The prime factorization of numbers in nums takes constant time due to the limited range (1 to 30). Space complexity is driven by the number of distinct prime factorizations, which is manageable due to the small number range. Modulo operations ensure manageable size of results.

What Interviewers Usually Probe

Can the candidate efficiently handle prime factorization for larger input sizes?
Is the candidate familiar with bit manipulation and dynamic programming?
Does the candidate handle modular arithmetic correctly in their solution?

Common Pitfalls or Variants

Common pitfalls

Overlooking the need for distinct prime factorizations can result in incorrect subset counting.
Not using modulo $10^9 + 7$ can cause overflow issues when dealing with large inputs.
Not optimizing prime factorization by considering only relevant numbers can lead to inefficient solutions.

Follow-up variants

Consider a variant where all numbers in nums are prime, and explore how the solution changes.
A version where you must find subsets that can be formed with exactly k distinct primes.
Handling constraints where nums contains larger numbers beyond 30 could add complexity.

FAQ

What is the key idea for solving 'The Number of Good Subsets'?

The key idea is to prime factorize the elements of the array and use bit manipulation to track subsets based on their prime factors.

How do I optimize the solution for large arrays?

Optimizing with dynamic programming and hash tables helps efficiently manage the subsets without iterating over all combinations.

What makes a subset 'good' in this problem?

A good subset is one whose product can be expressed as a product of distinct prime numbers.

Why is modulo $10^9 + 7$ necessary in this problem?

Modulo $10^9 + 7$ ensures the result stays within the limits of typical integer ranges and avoids overflow when dealing with large numbers.

Can this problem be solved without dynamic programming?

While it's possible to solve it without dynamic programming, the approach would be inefficient, especially for larger inputs, and would likely require more time to compute the subsets.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

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

Continue Practicing

#1799 maximize score after n operations #996 number of squareful arrays #2035 partition array into two arrays to minimize sum difference