2709. Count the Number of Square-Free Subsets
My accepted Python solution to LeetCode problem 2709, Count the Number of Square-Free Subsets, running in 483ms.
- Difficulty: Medium
- Python
- Runtime 483ms
- Memory 17.5MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 483ms, memory 17.5MB, accepted 2025-12-30.
class Solution:
def squareFreeSubsets(self, nums: List[int]) -> int:
MOD = 10**9 + 7
# Primes up to 30
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
# For each number, get its prime mask (or -1 if not square-free)
def get_mask(n):
mask = 0
for i, p in enumerate(primes):
if n % (p * p) == 0:
return -1 # Not square-free
if n % p == 0:
mask |= (1 << i)
return mask
# dp[mask] = number of ways to form subsets with prime mask
dp = [0] * (1 << len(primes))
dp[0] = 1 # empty subset
for num in nums:
if num == 1:
# 1 can be added to any subset
for mask in range((1 << len(primes)) - 1, -1, -1):
dp[mask] = (dp[mask] * 2) % MOD
else:
num_mask = get_mask(num)
if num_mask == -1:
continue # Skip numbers that are not square-free
# Update dp in reverse order to avoid counting same element twice
for mask in range((1 << len(primes)) - 1, -1, -1):
if (mask & num_mask) == 0:
dp[mask | num_mask] = (dp[mask | num_mask] + dp[mask]) % MOD
# Sum all non-empty subsets
return (sum(dp) - 1) % MOD