Formatted question description: https://leetcode.ca/all/1994.html
1994. The Number of Good Subsets
Level
Hard
Description
You are given an integer array nums
. We call a subset of nums
good if its product can be represented as a product of one or more distinct prime numbers.
- For example, if
nums = [1, 2, 3, 4]
:[2, 3]
,[1, 2, 3]
, and[1, 3]
are good subsets with products6 = 2*3
,6 = 2*3
, and3 = 3
respectively.[1, 4]
and[4]
are not good subsets with products4 = 2*2
and4 = 2*2
respectively.
Return the number of different good subsets in nums
modulo 10^9 + 7
.
A subset of nums
is any array that can be obtained by deleting some (possibly none or all) elements from nums
. Two subsets are different if and only if the chosen indices to delete are different.
Example 1:
Input: nums = [1,2,3,4]
Output: 6
Explanation: The good subsets are:
Example 2:
Input: nums = [4,2,3,15]
Output: 5
Explanation: The good subsets are:
Constraints:
1 <= nums.length <= 10^5
1 <= nums[i] <= 30
Solution
Use dynamic programming with compressed states. Obviously, each prime factor can occur at most once in a good subset, and if the number 1 is in nums
, the number 1 can occur any number of times as long as the subset contains at least one number that is greater than 1.
class Solution {
int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
public int numberOfGoodSubsets(int[] nums) {
final int MODULO = 1000000007;
int length = nums.length;
int[] states = new int[31];
for (int i = 1; i <= 30; i++)
states[i] = calculate(i);
int[] f = new int[1 << 10];
int[] g = new int[1 << 10];
int[] counts = new int[31];
for (int i = 0; i < length; i++)
counts[nums[i]]++;
if (counts[1] == length)
return 0;
f[0] = 1;
for (int i = 2; i <= 30; i++) {
int state = states[i];
if (state == -1 || counts[i] == 0)
continue;
for (int j = 0; j < 1 << 10; j++)
g[j] = f[j];
for (int j = 0; j < 1 << 10; j++) {
if (g[j] != 0 && (j & state) == 0) {
f[j ^ state] += (int) ((long) g[j] * counts[i] % MODULO);
f[j ^ state] %= MODULO;
}
}
}
int power = 1;
for (int i = 0; i < counts[1]; i++)
power = power * 2 % MODULO;
long sum = 0;
for (int i = 0; i < 1 << 10; i++)
sum += f[i];
sum += MODULO - 1;
sum %= MODULO;
sum = sum * power % MODULO;
return (int) sum;
}
public int calculate(int num) {
int state = 0;
for (int i = 0; i < 10; i++) {
if (num % primes[i] == 0) {
if ((num / primes[i]) % primes[i] == 0)
return -1;
state |= 1 << i;
}
}
return state;
}
}