1994. The Number of Good Subsets

Problem Description

You have an array of integers called nums. The task is to find the number of different subsets of nums that are considered "good." A "good" subset is one where the product of its elements can be written as the product of one or more distinct prime numbers. Specifically:

• If a subset's product includes a repeated prime factor (like 2 * 2), it's not a "good" subset.
• 1 has no prime factors and can be included in a "good" subset; it doesn't affect the product's prime factorization.
• Different subsets are defined as those made by deleting different elements from nums.

The answer must be provided modulo (10^9 + 7), which is a common way to keep the numbers from getting too large by using the remainder after division by a large prime number.

For example, in an array [1, 2, 3, 4], the subset [2, 3] is good because 2 * 3 = 6 (product of distinct primes), but [4] is not good, since 4 = 2 * 2 (repeated prime).

Intuition

The intuition behind the solution is rooted in combinatorics and bitwise operations. Firstly, notice that the maximum value in nums is specified as 30, which simplifies our problem since there are only a few primes within this range.

Here's how we can think about the problem:

1. Count the frequencies of each number in nums using a Counter.
2. Precalculate a list of primes that we will use to check against the elements in nums.
3. Use a bitmask to represent the inclusion of a certain prime factor in a subset product. For example, if the bitmask is 0101, it could represent that the product has prime factors of the 1st and 3rd prime numbers in our primes list.
4. Initialize an array f where f[i] (where i is a bitmask) will represent the number of ways to get a product that has the prime factors represented by the bitmask i.
5. Handle the special case for 1 separately, since it doesn't affect the product but it can be included or not, essentially doubling the number of subsets for each possible product.
6. Iterate through all numbers from 2 to 30 and for each, calculate their bitmask of prime factors if they have no repeated prime factors (like 4, 9, 25, etc., which are skipped).
7. Use dynamic programming to update the array f when considering the inclusion of each number with no repeated prime factors as you iterate through all possible states (bitmasks).
8. The final answer is the sum of all values of f except f[0], which is the empty subset, modulo 10^9 + 7.

The solution leverages bite masks to encode the presence of prime factors elegantly and uses dynamic programming to build up the counts of valid subsets, taking into account the combination of present factors without duplication.

Learn more about Math, Dynamic Programming and Bitmask patterns.

Solution Approach

The solution approach involves the following steps:

1. Count frequencies: Create a count of all the numbers nums using the Counter class from Python's collections. This step is necessary to handle duplicated numbers in nums.

   1cnt = Counter(nums)

2. Modulo arithmetic: Define the modulo mod = 10**9 + 7 because we want the results modulo 10^9 + 7.

   1mod = 10**9 + 7

3. Bitmasking for prime factors:

   • Define primes as an array of prime numbers that are less than 30 since the question limits the numbers in nums up to 30.
   • Create an array f with size 1 << len(primes) (which is 2^n where n is the number of primes). f uses bitmasks to represent subsets of primes included in the product. For example, f[0b1010] would represent the number of subsets whose product is made up of the 2nd and 4th prime numbers in the primes list.

   1primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
   2f = [0] * (1 << len(primes))

4. Handling the special case for number 1:

   • The product of any "good" subset doesn't change if we include or exclude 1. Thus, any subset that includes 1 can appear in 2^count[1] different ways. We initialize f[0] (which includes no prime factors) to this value.

   1f[0] = pow(2, cnt[1], mod)

5. Dynamic Programming:

   • Iterate through numbers x from 2 to 30. If a number has a square of a prime as a factor (like 4, 9, 25), we skip it since it is not a "good" subset.
   • Calculate the bitmask for the prime factors of x. If x is divisible by a prime at index i, we set the ith bit of mask to 1.
   • We then iterate through all possible states (from (1 << n) - 1 to 1) to update our f using dynamic programming. If a state contains all bits in the mask (checked with state & mask == mask), we can include x in this state. We then update f[state] by adding the ways to form the current product from the state without x times the count of x.
   • Finally, the f[state ^ mask] refers to the current state minus the prime factors of x.

   1for x in range(2, 31):
   2    if cnt[x] != 0 and x % 4 != 0 and x % 9 != 0 and x % 25 != 0:
   3        mask = 0
   4        for i, p in enumerate(primes):
   5            if x % p == 0: mask |= 1 << i
   6        for state in range((1 << n) - 1, 0, -1):
   7            if state & mask == mask:
   8                f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod

6. Deriving the answer:

   • Iterate over all f but skip the 0 state because it includes no primes. Sum the f[i] values to get the total number of "good" subsets, and take the result modulo mod.

   1answer = sum(f[i] for i in range(1, 1 << n)) % mod

7. The answer is returned as the final number of "good" subsets modulo 10^9 + 7.

By combining these steps—specifically the use of bitmasking, dynamic programming, and special handling for 1—the algorithm efficiently calculates the number of "good" subsets within the given constraints.

Example Walkthrough

Let's illustrate the solution approach using a small example: consider the array nums = [1, 2, 3, 4, 6].

1. Count frequencies: Using a Counter, we find that the frequencies are:

   1{1: 1, 2: 1, 3: 1, 4: 1, 6: 1}

2. Modulo arithmetic: The results are to be presented modulo mod = 10**9 + 7.

3. Bitmasking for prime factors:

   • Our primes array with primes less than 30 is [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].
   • We create an array f of size 1 << len(primes) (1024 in this case).

4. Handling the special case for number 1:

   • Since 1 doesn't affect the product's prime factorization, there are 2^count[1] = 2 ways to include it in any subset. We set f[0] = 2.

5. Dynamic Programming:

   • First we consider 2: it's a prime, so its bitmask is 0b0000000001. There are 1 way to have a subset with a product of 2 (ignoring 1 for now), so f[0b0000000001] = 1.
   • Next, 3 is prime and its bitmask is 0b0000000010. There is 1 way for a subset with a product of 3, so f[0b0000000010] = 1.
   • 4 is not considered because it's not a product of distinct primes, being 2 * 2.
   • For 6 (which is 2 * 3), its mask is 0b0000000011. However, there is no state to update yet that includes both 2 and 3, so f[0b0000000011] remains 0 for now.
   • At the end of the first iteration, f looks like this (showing non-zero values only):

     1f[0b0000000000] = 2  (from the special case of '1')
     2f[0b0000000001] = 1  (from '2')
     3f[0b0000000010] = 1  (from '3')

6. Deriving the answer:

   • Summing the non-zero f[i] values, we get 2 + 1 + 1 = 4, which we need to present modulo 10^9 + 7.

7. Final Answer: After iterating through the other numbers in nums and updating the f array accordingly, the final answer would be the sum of all valid f[i] values after completing the dynamic programming (modulo mod). In our small example case, we would need to continue the dynamic programming steps for 6, which would increase the count of f[0b0000000011], and then take the sum of the f array (excluding f[0]) modulo mod.

In a fully worked-through solution with the remaining numbers, we would use the above process to dynamically update the f array with all combinations of primes represented by the numbers in nums. This method ensures, through the use of bitmasks and the dynamic array f, that only "good" subsets (those with unique prime factors) are considered in the final count, adhering to the rules of the problem.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by several nested loops and operations on the Counter object.

1. Counting the frequency of each number takes O(n), where n is the length of the nums list.
2. Calculating pow(2, cnt[1], mod) is O(log(cnt[1])), which is the complexity of the exponentiation operation.
3. The loop from 2 to 30 for each number x is run 29 times (O(1) since it's a constant), and within this loop:
   • Checking whether x is divisible by 4, 9, or 25 is O(1).
   • Constructing the mask requires iterating over the list of primes, which is O(m) where m is the number of primes (len(primes)).
4. The most significant loop is the nested loop that iterates over all states of the f array. There are (1 << n) states, which is 2^n, iterated for each x. The bitwise operations inside the loop are O(1) operations. Therefore, the nested loop's complexity is O(2^n * m).

Overall, the most time-consuming part is the nested loop with a complexity of O(2^n * m), where n is the number of primes considered (n = 10 here) and m is the count of numbers between 2 and 30 for which frequency is calculated. Consequently, the overall time complexity is O(2^n * m) which simplifies to O(2^10 * 29).

Space Complexity

The space complexity of the code is determined by the additional data structures that are used:

1. The cnt Counter object has at most 30 key-value pairs corresponding to the numbers from 1 to 30, thus O(1) space.
2. The f array has (1 << n) elements, which is 2^n, yielding O(2^n) space complexity.

The dominant factor is the space required for the f array. Hence, the overall space complexity is O(2^n), where n is the number of primes.

Learn more about how to find time and space complexity quickly using problem constraints.