2572. Count the Number of Square-Free Subsets
Approach
Bitmask DP. Represent each number as a bitmask over the 10 primes ≤ 30.
A number is invalid if any prime divides it twice. Use DP over subsets: dp[i][mask] =
ways to pick subsets of nums[0..i] using exactly the primes in 'mask'.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Math problems test number theory, combinatorics, and modular arithmetic. Common tools: GCD/LCM (Euclidean algorithm), prime sieve, modular inverse (Fermat's little theorem), digit manipulation, and bit tricks. Overflow is a key concern in C# — use long when products may exceed 2³¹.
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
// Approach: Bitmask DP. Represent each number as a bitmask over the 10 primes ≤ 30.
// A number is invalid if any prime divides it twice. Use DP over subsets: dp[i][mask] =
// ways to pick subsets of nums[0..i] using exactly the primes in 'mask'.
// Time: O(n * 2^10) Space: O(n * 2^10)
public class Solution
{
private const int kMod = 1000000007;
private const int kPrimesCount = 10;
private static readonly int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
public int SquareFreeSubsets(int[] nums)
{
int[][] mem = new int[nums.Length][];
for (int i = 0; i < nums.Length; i++)
{
int[] row = new int[1 << (kPrimesCount + 1)];
Array.Fill(row, -1);
mem[i] = row;
}
int[] masks = new int[nums.Length];
for (int i = 0; i < nums.Length; ++i)
masks[i] = GetMask(nums[i]);
// -1 means that we take no number.
// `used` is initialized to 1 so that -1 & 1 = 1 instead of 0.
return (SquareFreeSubsets(masks, 0, /*used=*/1, mem) - 1 + kMod) % kMod;
}
private int SquareFreeSubsets(int[] masks, int i, int used, int[][] mem)
{
if (i == masks.Length)
return 1;
if (mem[i][used] != -1)
return mem[i][used];
int pick = (masks[i] & used) == 0 ? SquareFreeSubsets(masks, i + 1, used | masks[i], mem) : 0;
int skip = SquareFreeSubsets(masks, i + 1, used, mem);
return mem[i][used] = (pick + skip) % kMod;
}
// e.g. num = 10 = 2 * 5, so mask = 0b101 -> 0b1010 (append a 0)
// num = 15 = 3 * 5, so mask = 0b110 -> 0b1100 (append a 0)
// num = 25 = 5 * 5, so mask = 0b-1 -> 0b1..1 (invalid)
private int GetMask(int num)
{
int mask = 0;
for (int i = 0; i < primes.Length; ++i)
{
int rootCount = 0;
while (num % primes[i] == 0)
{
num /= primes[i];
++rootCount;
}
if (rootCount >= 2)
return -1;
if (rootCount == 1)
mask |= 1 << i;
}
return mask << 1;
}
}