Solution: The Number of Good Subsets

Explore how to efficiently count good subsets in an integer array by ensuring each subset's product has distinct prime factors. Learn to implement a dynamic programming solution with bit masks that manages prime factor combinations without checking every subset explicitly. This lesson teaches you how to handle frequency counts, validate square-free numbers, and apply modulo arithmetic for large results, preparing you for complex coding interview challenges.

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]$ ...