Welcome to Subscribe On Youtube

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;
    }
}

############

class Solution {
    public int numberOfGoodSubsets(int[] nums) {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        int[] cnt = new int[31];
        for (int x : nums) {
            ++cnt[x];
        }
        final int mod = (int) 1e9 + 7;
        int n = primes.length;
        long[] f = new long[1 << n];
        f[0] = 1;
        for (int i = 0; i < cnt[1]; ++i) {
            f[0] = (f[0] * 2) % mod;
        }
        for (int x = 2; x < 31; ++x) {
            if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
                continue;
            }
            int mask = 0;
            for (int i = 0; i < n; ++i) {
                if (x % primes[i] == 0) {
                    mask |= 1 << i;
                }
            }
            for (int state = (1 << n) - 1; state > 0; --state) {
                if ((state & mask) == mask) {
                    f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod;
                }
            }
        }
        long ans = 0;
        for (int i = 1; i < 1 << n; ++i) {
            ans = (ans + f[i]) % mod;
        }
        return (int) ans;
    }
}

  • // OJ: https://leetcode.com/problems/the-number-of-good-subsets/
// Time: O(30 * 2^10)
// Space: O(2^10)
constexpr long mod = 1000000007;
int mask[31] = { -1, 0, 1, 2, -1, 4, 3, 8, -1, -1, 5, 16, -1, 32, 9, 6, -1, 64, -1, 128, -1, 10, 17, 256, -1, -1, 33, -1, -1, 512, 7 };
class Solution {
public:
    int numberOfGoodSubsets(vector<int>& A) {
        long dp[1025] = { 1 }, cnt[31] = {};
        for (int n : A) ++cnt[n];
        for (int i = 2; i <= 30; ++i) {
            if (mask[i] == -1 || cnt[i] == 0) continue;
            for (int mi = mask[i], mj = 0; mj < 1024; ++mj) {
                dp[mi | mj] = (dp[mi | mj] + cnt[i] * dp[mj] * ((mi & mj) == 0)) % mod;
            }
        }
        int ans = accumulate(begin(dp) + 1, end(dp), 0, [](int s, int n) { return (s + n) % mod; });
        while (cnt[1]--) ans = (ans << 1) % mod;
        return ans;
    }
};

  • class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        counter = Counter(nums)
        mod = 10**9 + 7
        prime = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        n = len(prime)
        dp = [0] * (1 << n)
        dp[0] = 1
        for x in range(2, 31):
            if counter[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0:
                continue
            mask = 0
            for i, p in enumerate(prime):
                if x % p == 0:
                    mask |= 1 << i
            for state in range(1 << n):
                if mask & state:
                    continue
                dp[mask | state] = (dp[mask | state] + counter[x] * dp[state]) % mod
        ans = 0
        for i in range(1, 1 << n):
            ans = (ans + dp[i]) % mod
        for i in range(counter[1]):
            ans = (ans << 1) % mod
        return ans



  • func numberOfGoodSubsets(nums []int) (ans int) {
	primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
	cnt := [31]int{}
	for _, x := range nums {
		cnt[x]++
	}
	const mod int = 1e9 + 7
	n := 10
	f := make([]int, 1<<n)
	f[0] = 1
	for i := 0; i < cnt[1]; i++ {
		f[0] = f[0] * 2 % mod
	}
	for x := 2; x < 31; x++ {
		if cnt[x] == 0 || x%4 == 0 || x%9 == 0 || x%25 == 0 {
			continue
		}
		mask := 0
		for i, p := range primes {
			if x%p == 0 {
				mask |= 1 << i
			}
		}
		for state := 1<<n - 1; state > 0; state-- {
			if state&mask == mask {
				f[state] = (f[state] + f[state^mask]*cnt[x]) % mod
			}
		}
	}
	for i := 1; i < 1<<n; i++ {
		ans = (ans + f[i]) % mod
	}
	return
}

All Problems

All Solutions