Count the Number of Square-Free Subsets

medium dp bitmask

Problem

Given an array nums of positive integers (each 1..30), count the non-empty subsets whose product is square-free (no prime appears with exponent ≥ 2). Return the count modulo 10^9 + 7.

Inputnums = [3,4,4,5]

Output3

4 is not square-free, so it is unusable. The square-free non-empty subsets are {3}, {5}, {3,5}.

nums (1..30)

def square_free_subsets(nums):
    MOD = 10**9 + 7
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

    def mask_of(x):
        m = 0
        for b, p in enumerate(primes):
            if x % p == 0:
                if x % (p * p) == 0:
                    return -1            # not square-free
                m |= 1 << b
        return m

    dp = [0] * (1 << len(primes))
    dp[0] = 1                            # empty subset
    for x in nums:
        m = mask_of(x)
        if m == -1:
            continue
        for s in range((1 << len(primes)) - 1, -1, -1):
            if (s & m) == 0:             # disjoint primes -> can add x
                dp[s | m] = (dp[s | m] + dp[s]) % MOD
    return (sum(dp) - 1) % MOD           # subtract the empty subset

function squareFreeSubsets(nums) {
  const MOD = 1000000007n;
  const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
  const maskOf = (x) => {
    let m = 0;
    for (let b = 0; b < primes.length; b++) {
      const p = primes[b];
      if (x % p === 0) {
        if (x % (p * p) === 0) return -1;
        m |= 1 << b;
      }
    }
    return m;
  };
  const dp = new Array(1 << primes.length).fill(0n);
  dp[0] = 1n;
  for (const x of nums) {
    const m = maskOf(x);
    if (m === -1) continue;
    for (let s = dp.length - 1; s >= 0; s--) {
      if ((s & m) === 0) dp[s | m] = (dp[s | m] + dp[s]) % MOD;
    }
  }
  let total = 0n;
  for (const v of dp) total = (total + v) % MOD;
  return Number((total - 1n + MOD) % MOD);
}

class Solution {
    public int squareFreeSubsets(int[] nums) {
        long MOD = 1_000_000_007L;
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        long[] dp = new long[1 << primes.length];
        dp[0] = 1;
        for (int x : nums) {
            int m = 0;
            boolean ok = true;
            for (int b = 0; b < primes.length; b++) {
                int p = primes[b];
                if (x % p == 0) {
                    if (x % (p * p) == 0) { ok = false; break; }
                    m |= 1 << b;
                }
            }
            if (!ok) continue;
            for (int s = dp.length - 1; s >= 0; s--) {
                if ((s & m) == 0) dp[s | m] = (dp[s | m] + dp[s]) % MOD;
            }
        }
        long total = 0;
        for (long v : dp) total = (total + v) % MOD;
        return (int) ((total - 1 + MOD) % MOD);
    }
}

int squareFreeSubsets(vector<int>& nums) {
    const long long MOD = 1000000007LL;
    int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int P = 10;
    vector<long long> dp(1 << P, 0);
    dp[0] = 1;
    for (int x : nums) {
        int m = 0; bool ok = true;
        for (int b = 0; b < P; b++) {
            int p = primes[b];
            if (x % p == 0) {
                if (x % (p * p) == 0) { ok = false; break; }
                m |= 1 << b;
            }
        }
        if (!ok) continue;
        for (int s = (1 << P) - 1; s >= 0; s--) {
            if ((s & m) == 0) dp[s | m] = (dp[s | m] + dp[s]) % MOD;
        }
    }
    long long total = 0;
    for (long long v : dp) total = (total + v) % MOD;
    return (int) ((total - 1 + MOD) % MOD);
}

Explanation

A product is square-free when no prime divides it twice. Since every value is at most 30, only the ten primes 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 can ever appear. We encode the set of primes dividing a number as a 10-bit mask.

First we map each value to its prime mask. If a number is itself divisible by some p² (like 4, 8, 9, 12, …) it can never sit in a square-free product, so we drop it. The number 1 maps to the empty mask and acts as a free multiplier.

The DP array dp[s] counts subsets whose combined prime set is exactly s. Starting from dp[0] = 1 (the empty subset), for each usable number with mask m we look at every state s that shares no prime with m (s & m == 0) and add those counts into dp[s | m].

We sweep s from high to low so each number is only used once per subset (0/1-knapsack style). At the end sum(dp) counts all square-free subsets including the empty one, so we subtract 1.

Example: nums = [3,4,4,5]. Both 4s are dropped (divisible by 2²). Combining masks for 3 and 5 yields subsets {3}, {5}, {3,5} → answer 3.

Time: O(n · 2^10) Space: O(2^10)