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 products 6 = 2*3, 6 = 2*3, and 3 = 3 respectively.
  • [1, 4] and [4] are not good subsets with products 4 = 2*2 and 4 = 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;
    }
}

All Problems

All Solutions