Solution: The Number of Good Subsets

Explore how to count the number of good subsets from an integer array, where each subset's product is composed of distinct prime factors. Understand the use of prime factorization, bit masks, and dynamic programming to efficiently solve the problem without enumerating all subsets. This lesson guides you through building and combining prime factor masks to ensure no duplicates, applying memoization, and handling edge cases like the number 1 to compute results under modulo conditions.

We'll cover the following...

Statement
Solution
- Time complexity
- Space complexity

Statement

For a given integer array, nums, you can say that a subset of nums is called “good” if the product of its elements can be expressed as a product of one or more distinct prime numbers, i.e., no prime factor appears more than once.

For example, if nums $= [1, 2, 5, 6]$ , then:

$[2, 5]$ , $[1, 2, 5]$ , and $[6]$ are good subsets with products $2 \times 5 = 10$ , $1 \times 2 \times 5 = 10$ , and $2 \times 3 = 6$ , respectively.
$[2, 6]$ ...