Counting Subsets With Products of Distinct Primes (Dynamic Programming + Bitmask)

Sandhiya Priya
2w
1.4k
0
1

Article

Problem Statement

Given an integer array arr[], count the number of subsets whose product can be represented as a product of one or more distinct prime numbers.

A subset is valid if its product is square-free, i.e., no prime factor appears more than once.

Different array indices are considered different subsets.

Return the answer modulo 10^9 + 7.

Example 1

Input

arr = [1, 2, 3, 4]

Possible subsets:

Subset	Product	Valid?	Reason
[2]	2	YES	Prime
[3]	3	YES	Prime
[1,2]	2	YES	1 doesn't affect product
[1,3]	3	YES	1 doesn't affect product
[2,3]	6	YES	2 × 3
[1,2,3]	6	YES	2 × 3
[4]	4	NO	2² (repeated prime)
[2,4]	8	NO	2³

Answer = 6

Example 2

arr = [2,2,3]

Valid subsets

[2(first)]
[2(second)]
[3]
[2(first),3]
[2(second),3]

Answer = 5

Observation 1

The maximum value in the array is only 30.

So we only have these prime numbers:

Only 10 primes.

This is the biggest hint of the problem.

Instead of storing prime factors in a large structure, we can store them inside 10 bits.

Observation 2

A number is useful only if it is square-free.

Valid

2
3
5
6 = 2×3
10 = 2×5
30 = 2×3×5

Every prime appears once.

Invalid

4 = 2²
8 = 2³
9 = 3²
12 = 2²×3
18 = 2×3²
20 = 2²×5

These contain repeated primes.

We ignore them completely.

Step 1: Create Prime Masks

Assign one bit to each prime.

Prime	Bit
2	0
3	1
5	2
7	3
11	4
13	5
17	6
19	7
23	8
29	9

Example

Number = 6

Prime factors:

6 = 2 × 3

Mask:

bit0 = 1
bit1 = 1

Mask = 0000000011

Number = 10

10 = 2 × 5

Mask:

Number = 30

30 = 2×3×5

Mask:

Number = 4

4 = 2²

Repeated prime.

Not allowed.

Discard it.

Code Explanation (Mask Creation)

for (int x = 2; x <= 30; x++) {

    int t = x;
    int mask = 0;
    boolean ok = true;

    for (int i = 0; i < 10; i++) {

        int p = primes[i];
        int cnt = 0;

        while (t % p == 0) {
            cnt++;
            t /= p;
        }

        if (cnt > 1) {
            ok = false;
            break;
        }

        if (cnt == 1)
            mask |= (1 << i);
    }

    if (ok) {
        valid[x] = true;
        masks[x] = mask;
    }
}

Explanation

Take every number from 2 to 30.

Suppose:

x = 6

Initially:

mask = 0000000000

Check prime 2:

6 divisible by 2

cnt = 1

mask = 0000000001

Check prime 3:

cnt = 1

mask = 0000000011

No repeated prime.

Store:

mask[6] = 3

Suppose:

x = 12

Factorization:

12 = 2×2×3

Prime 2 occurs twice.

cnt = 2

Therefore:

ok = false;

Number is discarded.

Step 2: Count Frequency

int[] freq = new int[31];

for(int x : arr)
    freq[x]++;

Instead of processing:

five times,

we store:

freq[2]=5

This makes the solution much faster.

Step 3: DP Definition

dp[mask]

Meaning

Number of ways to create subsets whose used primes equal mask.

Initially:

dp[0]=1;

Why?

Because:

Empty subset

contains no primes.

Step 4: Transition

Suppose current number is:

Mask:

Current DP mask:

This means:

Prime used:

No overlap.

1000
0011
----
0000

Safe to add.

New mask:

1000
0011
----
1011

Transition:

next[newMask]+=dp[oldMask];

Suppose current mask:

Current number:

Overlap:

0010
0011
----
0010

Not zero.

Prime 3 repeats.

Cannot add.

This is checked by:

if((mask & m)==0)

Code Explanation

for(int num=2;num<=30;num++){

    if(!valid[num] || freq[num]==0)
        continue;

    int m=masks[num];

    long[] next=dp.clone();

    for(int mask=0;mask<(1<<10);mask++){

        if(dp[mask]==0)
            continue;

        if((mask&m)==0){

            int newMask=mask|m;

            next[newMask]+=dp[mask]*freq[num];
        }
    }

    dp=next;
}

Why Clone DP?

Imagine:

Current DP:

mask0
mask1
mask2

While processing one number, we must use old states only.

If we directly modify dp, the same number may be counted multiple times in one iteration.

So we copy:

next = dp.clone();

After finishing:

dp = next;

This is the standard 0/1 Knapsack technique.

Step 5: Why Multiply by Frequency?

Suppose:

arr=[2,2,2]

There are three different indices.

Choosing:

First 2
Second 2
Third 2

are different subsets.

So:

dp[mask] * freq[num]

counts all possible index choices.

Step 6: Handling Ones

The number:

has no prime factor.

It never changes the mask.

If there are:

k ones

each valid subset can choose:

Take none
Take first
Take second
Take both
...

Total possibilities:

2^k

Therefore:

answer *= 2^ones

Example

arr=[1,1,2]

Subset:

[2]

can become:

[2]
[1,2]
[1,2]
[1,1,2]

Exactly:

2² = 4

possibilities.

Step 7: Final Answer

Ignore:

dp[0]

because it represents:

Empty subset

Answer:

for(mask=1;mask<(1<<10);mask++)
    ans+=dp[mask];

ans*=2^ones;

Dry Run

Input

arr=[1,2,3]

Frequency

1 → 1
2 → 1
3 → 1

Initially:

dp[0]=1

Process 2:

dp[1]=1

Process 3:

dp[2]=1
dp[3]=1

Meaning:

mask1 -> {2}
mask2 -> {3}
mask3 -> {2,3}

Total:

There is one 1.

Multiply by:

2¹=2

Answer:

Subsets:

[2]
[3]
[2,3]
[1,2]
[1,3]
[1,2,3]

Correct.

Time Complexity

Building masks: O(30 × 10) ≈ O(1)
Frequency counting: O(n)
DP: 30 × 2¹⁰ = 30 × 1024 ≈ 30,720 operations

Overall:

Time Complexity: O(n)

Space Complexity

Frequency array: O(31)
Mask array: O(31)
DP array: O(2¹⁰) = O(1024)

Overall:

Space Complexity: O(1024) ≈ O(1)

Key Takeaways

Since values are limited to 30, only 10 distinct primes are relevant.
Represent each number's prime factors using a 10-bit mask.
Discard numbers with repeated prime factors because they can never produce a square-free product.
Use Bitmask DP to ensure no prime is used more than once in any subset.
Handle duplicate values using their frequency, since different indices form different subsets.
Treat 1 separately because it doesn't affect the product; multiply the final count by 2^(number of ones).

Summary

The solution leverages the small value range (1 to 30) by representing prime factors as a 10-bit mask and using Bitmask Dynamic Programming to efficiently count all square-free subsets. Invalid numbers with repeated prime factors are discarded, duplicate values are handled through frequency counting, and the contribution of 1s is applied at the end. This approach achieves O(n) time complexity with only 1024 DP states, making it efficient even for arrays containing up to 100,000 elements.