Solution: The Number of Good Subsets

Explore how to count the number of good subsets in an integer array such that the product of elements contains no repeated prime factors. Learn to apply dynamic programming combined with bit masking to efficiently track prime factors and evaluate subsets. Understand how to handle duplicates and the number one separately to optimize the counting process, and how to manage time and space complexity for large input arrays.

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