Tap here to switch tabs
Problem
Submissions

Problem: The Number of Good Subsets

The Number of Good Subsets asks you to count array subsets whose product is made of distinct prime numbers. Different chosen indexes count separately; return the result modulo a large prime.

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]= [1, 2, 5, 6], then:

  • [2,5][2, 5], [1,2,5][1, 2, 5], and [6][6] are good subsets with products 2×5=102 \times 5 = 10, 1×2×5=101 \times 2 \times 5 = 10, and 2×3=62 \times 3 = 6, respectively.

  • [2,6][2, 6] and [1,2,6][1, 2, 6] are not good subsets as their products are 2×2×3=122 \times 2 \times 3 = 12, which repeats a prime factor.

Your task is to return the number of different good subsets in nums modulo 109+710^9 + 7.

A subset is formed by deleting zero or more elements from nums. Two subsets are considered different if they are formed by deleting different indexes.

Constraints:

  • 1≤1 \leq nums.length ≤105\leq 10^5

  • 1≤1 \leq nums[i] ≤30\leq 30

⋮
Tap here to switch tabs
Problem
Submissions

Problem: The Number of Good Subsets

The Number of Good Subsets asks you to count array subsets whose product is made of distinct prime numbers. Different chosen indexes count separately; return the result modulo a large prime.

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]= [1, 2, 5, 6], then:

  • [2,5][2, 5], [1,2,5][1, 2, 5], and [6][6] are good subsets with products 2×5=102 \times 5 = 10, 1×2×5=101 \times 2 \times 5 = 10, and 2×3=62 \times 3 = 6, respectively.

  • [2,6][2, 6] and [1,2,6][1, 2, 6] are not good subsets as their products are 2×2×3=122 \times 2 \times 3 = 12, which repeats a prime factor.

Your task is to return the number of different good subsets in nums modulo 109+710^9 + 7.

A subset is formed by deleting zero or more elements from nums. Two subsets are considered different if they are formed by deleting different indexes.

Constraints:

  • 1≤1 \leq nums.length ≤105\leq 10^5

  • 1≤1 \leq nums[i] ≤30\leq 30