Count the Number of Square-Free Subsets

Count the Number of Square-Free Subsets

What is this problem about?

The Count the Number of Square-Free Subsets interview question asks you to find the number of non-empty subsets of an array such that the product of elements in the subset is a "square-free" integer. A number is square-free if no prime factor appears more than once in its prime factorization (i.e., it is not divisible by any square $> 1$).

For example, 6 ($2 imes 3$) is square-free, but 12 ($2^2 imes 3$) is not.

Why is this asked in interviews?

This "Medium/Hard" problem from Media.net and Google tests bitmask dynamic programming and number theory. Since the elements are typically small ($\le 30$), there are only a few primes to consider. It evaluations whether a candidate can represent the prime factorization of a number as a bitmask and use DP to ensure no two numbers in a subset share a prime factor.

Algorithmic pattern used

The problem is solved using Bitmask DP.

1. Identify Primes: The primes $\le 30$ are [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] (10 total).
2. Pre-filter: Ignore any input number that is not square-free (e.g., 4, 8, 9, 12...).
3. Map to Masks: For each square-free number, create a 10-bit mask where the $i$-th bit is 1 if the $i$-th prime divides the number.
4. DP State: dp[mask] is the number of subsets whose product has prime factors represented by mask.
5. Transition: For each number with num_mask, update dp[new_mask | num_mask] += dp[new_mask] for all new_mask that don't overlap with num_mask.
6. Handle duplicate numbers by counting frequencies first.

Example explanation

nums = [2, 3, 6]

1. Primes: {2, 3...}. 2 is mask 01, 3 is mask 10, 6 is mask 11.
2. dp[00] = 1 (empty).
3. Process 2: dp[01] = 1.
4. Process 3:
   • dp[10] += dp[00] (Sub {3})
   • dp[11] += dp[01] (Sub {2, 3})
5. Process 6:
   • dp[11] already has factors 2 and 3. Cannot add 6 to any mask except 00.
   • dp[11] += dp[00] (Sub {6}) Total subsets = $dp[01] + dp[10] + dp[11] = 1 + 1 + 2 = 4$. ({2}, {3}, {2,3}, {6}).

Common mistakes candidates make

• Including non-square-free numbers: Forgetting to discard 4, 9, 16 etc. from the start.
• Complexity: Trying to use $2^N$ subset generation instead of bitmask DP.
• Handling 1s: Forgetting that '1' can be added to any square-free subset any number of times (contributes $2^{count(1)}$ multiplier).

Interview preparation tip

Whenever a problem involves "product property X" and the numbers are small, think about prime factor bitmasks. A bitmask of length 10 is very manageable for DP.