Subsets with Products of Distinct Primes

Problem Overview

Count subsets whose product is square-free (a product of distinct primes), modulo 1e9+7.

Intuition

Count subsets whose product is square-free (a product of distinct primes), modulo 1e9+7. Values are only 1..30, so there are 10 primes and every valid number is a small bit mask of those primes. Numbers with a squared factor (4, 8, 9, 12, ...) cannot appear. Ones are free multipliers: each 1 may be taken or not without changing the product.

Algorithm

1Count frequency of each value in 1..30.
2For i = 2..30, factor using the 10 primes; if any prime repeats, mark invalid; else store the prime bit mask.
3dp[mask] = ways to form a non-empty prime usage mask (dp[0] = 1 for empty).
4For each valid i with freq[i] > 0: for every state m disjoint from mask[i], add dp[m] * freq[i] into next[m | mask[i]].
5Sum dp[1..1023], then multiply by 2^freq[1] for optional ones. Return modulo 1e9+7.

Example Walkthrough

Input: arr = [1, 2, 3, 4]

1. 4 is invalid (2^2). Valid numbers: 2 (mask bit0), 3 (bit1).
2. Good subsets of {2,3}: {2}, {3}, {2,3}.
3. Each can optionally include the single 1, doubling the count: 3 * 2 = 6.

Output: 6

Common Pitfalls

• Skip non-square-free numbers; their mask stays 0 and they must not enter DP.
• Ones are handled after DP - do not put 1 into the mask DP.
• Clone/update carefully so the same number type is not applied twice on overlapping states in one pass.
• Subtract or omit the empty subset; only non-empty good subsets count.
• Answer can be large - always take modulo 1e9+7.

Subsets with Products of Distinct Primes.java

Java


class Solution {

    // Approach: Count values 1..30. Map each square-free number 2..30 to a bit
    // mask of its distinct primes (10 primes under 30). DP over used-prime masks:
    // for each number, add it onto states that share no primes. Ones multiply the
    // answer by 2^freq[1] since they do not change the product. Exclude empty.
    // Complexity: O(30 * 2^10) time and O(2^10) space after an O(n) frequency pass.
    int mod = (int) 1e9 + 7;

    public int countSubsets(int[] arr) {
        // code here
        int[] freq = new int[31];
        for (int x : arr) {
            freq[x]++;
        }

        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        int[] mask = new int[31];

        for (int i = 2; i <= 30; i++) {
            int x = i;
            int m = 0;
            boolean ok = true;

            for (int j = 0; j < 10; j++) {
                int p = prime[j];
                int cnt = 0;
                while (x % p == 0) {
                    cnt++;
                    x /= p;
                }
                if (cnt > 1) {
                    ok = false;
                    break;
                }
                if (cnt == 1) {
                    m |= (1 << j);
                }
            }

            if (ok) {
                mask[i] = m;
            }
        }

        long[] dp = new long[1024];
        dp[0] = 1;

        for (int i = 2; i <= 30; i++) {
            if (freq[i] == 0 || mask[i] == 0) {
                continue;
            }
            long[] next = dp.clone();
            for (int m = 0; m < 1024; m++) {
                if ((m & mask[i]) == 0) {
                    next[m | mask[i]] = (next[m | mask[i]] + dp[m] * freq[i]) % mod;
                }
            }
            dp = next;
        }

        long ans = 0;
        for (int i = 1; i < 1024; i++) {
            ans = (ans + dp[i]) % mod;
        }

        long ones = 1;
        for (int i = 0; i < freq[1]; i++) {
            ones = (ones * 2) % mod;
        }

        return (int) ((ans * ones) % mod);
    }
}

Was this solution helpful?