Solution: The Number of Good Subsets

Discover how to solve the problem of counting good subsets from an integer array where each subset's product has distinct prime factors. This lesson teaches you to use dynamic programming combined with prime factor bitmasks efficiently, avoiding brute-force approaches. Understand how to manage frequency counts, validate numbers for square-free properties, and apply modular arithmetic. By the end, you'll grasp the process to implement an optimized solution essential for advanced coding interviews.

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