Count the Number of Square-Free Subsets
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given a positive integer 0-indexed array nums.
A subset of the array nums is square-free if the product of its elements is a square-free integer.
A square-free integer is an integer that is divisible by no square number other than 1.
Return the number of square-free non-empty subsets of the array nums.
Since the answer may be too large, return it modulo 10^9 + 7.
A non-empty subset of nums is an array that can be obtained by deleting some (possibly none but not all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different.
Examples
Example 1
Input: nums = [3,4,4,5]
Output: 3
Explanation: There are 3 square-free subsets in this example:
- The subset consisting of the 0th element [3]. The product of its elements is 3, which is a square-free integer.
- The subset consisting of the 3rd element [5]. The product of its elements is 5, which is a square-free integer.
- The subset consisting of 0th and 3rd elements [3,5]. The product of its elements is 15, which is a square-free integer.
It can be proven that there are no more than 3 square-free subsets in the given array.
Example 2
Input: nums = [1]
Output: 1
Explanation: There is 1 square-free subset in this example:
- The subset consisting of the 0th element [1]. The product of its elements is 1, which is a square-free integer.
It can be proven that there is no more than 1 square-free subset in the given array.
Constraints
1 <= nums.length <= 10001 <= nums[i] <= 30
Solution
Method 1 – Bitmask Dynamic Programming
Intuition
A square-free integer is not divisible by any perfect square > 1. For numbers up to 30, we can precompute which numbers are square-free and their prime factors. We use bitmask DP to count valid subsets, ensuring no two numbers in a subset share a prime factor (which would introduce a square factor).
Approach
- Precompute for each number 1-30:
- If it is square-free (not divisible by any square > 1)
- Its prime factor bitmask (for the first 10 primes up to 30)
- Count the frequency of each number in nums.
- Use DP:
- dp[mask]: number of ways to form a subset with used primes as mask
- For each number, for each mask, if its prime mask does not overlap, update dp[mask | prime_mask]
- Handle 1s separately (since 1 is square-free and can be included any number of times)
- Sum all non-empty dp states and multiply by the number of ways to pick 1s.
Code
C++
class Solution {
public:
int countSquareFreeSubsets(vector<int>& nums) {
const int MOD = 1e9+7;
vector<int> primes = {2,3,5,7,11,13,17,19,23,29};
vector<int> numMask(31, 0);
for (int i = 2; i <= 30; ++i) {
int x = i, mask = 0, ok = 1;
for (int j = 0; j < primes.size(); ++j) {
int cnt = 0;
while (x % primes[j] == 0) {
x /= primes[j];
cnt++;
}
if (cnt > 1) ok = 0;
if (cnt) mask |= (1 << j);
}
if (ok) numMask[i] = mask;
}
vector<int> freq(31);
for (int x : nums) freq[x]++;
vector<long long> dp(1 << 10);
dp[0] = 1;
for (int i = 2; i <= 30; ++i) {
if (!numMask[i] || !freq[i]) continue;
for (int mask = (1 << 10) - 1; mask >= 0; --mask) {
if ((mask & numMask[i]) == 0) {
dp[mask | numMask[i]] = (dp[mask | numMask[i]] + dp[mask] * freq[i]) % MOD;
}
}
}
long long ans = 0;
for (int mask = 1; mask < (1 << 10); ++mask) ans = (ans + dp[mask]) % MOD;
int ones = freq[1];
long long pow2 = 1;
for (int i = 0; i < ones; ++i) pow2 = pow2 * 2 % MOD;
ans = ans * pow2 % MOD;
ans = (ans + pow2 - 1 + MOD) % MOD;
return ans;
}
};
Go
func countSquareFreeSubsets(nums []int) int {
MOD := int(1e9 + 7)
primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
numMask := make([]int, 31)
for i := 2; i <= 30; i++ {
x, mask, ok := i, 0, true
for j, p := range primes {
cnt := 0
for x%p == 0 {
x /= p
cnt++
}
if cnt > 1 {
ok = false
}
if cnt > 0 {
mask |= 1 << j
}
}
if ok {
numMask[i] = mask
}
}
freq := make([]int, 31)
for _, x := range nums {
freq[x]++
}
dp := make([]int, 1<<10)
dp[0] = 1
for i := 2; i <= 30; i++ {
if numMask[i] == 0 || freq[i] == 0 {
continue
}
for mask := (1 << 10) - 1; mask >= 0; mask-- {
if mask&numMask[i] == 0 {
dp[mask|numMask[i]] = (dp[mask|numMask[i]] + dp[mask]*freq[i]) % MOD
}
}
}
ans := 0
for mask := 1; mask < (1 << 10); mask++ {
ans = (ans + dp[mask]) % MOD
}
ones := freq[1]
pow2 := 1
for i := 0; i < ones; i++ {
pow2 = pow2 * 2 % MOD
}
ans = ans * pow2 % MOD
ans = (ans + pow2 - 1 + MOD) % MOD
return ans
}
Java
class Solution {
public int countSquareFreeSubsets(int[] nums) {
int MOD = 1_000_000_007;
int[] primes = {2,3,5,7,11,13,17,19,23,29};
int[] numMask = new int[31];
for (int i = 2; i <= 30; ++i) {
int x = i, mask = 0;
boolean ok = true;
for (int j = 0; j < primes.length; ++j) {
int cnt = 0;
while (x % primes[j] == 0) {
x /= primes[j];
cnt++;
}
if (cnt > 1) ok = false;
if (cnt > 0) mask |= (1 << j);
}
if (ok) numMask[i] = mask;
}
int[] freq = new int[31];
for (int x : nums) freq[x]++;
long[] dp = new long[1 << 10];
dp[0] = 1;
for (int i = 2; i <= 30; ++i) {
if (numMask[i] == 0 || freq[i] == 0) continue;
for (int mask = (1 << 10) - 1; mask >= 0; --mask) {
if ((mask & numMask[i]) == 0) {
dp[mask | numMask[i]] = (dp[mask | numMask[i]] + dp[mask] * freq[i]) % MOD;
}
}
}
long ans = 0;
for (int mask = 1; mask < (1 << 10); ++mask) ans = (ans + dp[mask]) % MOD;
int ones = freq[1];
long pow2 = 1;
for (int i = 0; i < ones; ++i) pow2 = pow2 * 2 % MOD;
ans = ans * pow2 % MOD;
ans = (ans + pow2 - 1 + MOD) % MOD;
return (int)ans;
}
}
Kotlin
class Solution {
fun countSquareFreeSubsets(nums: IntArray): Int {
val MOD = 1_000_000_007
val primes = intArrayOf(2,3,5,7,11,13,17,19,23,29)
val numMask = IntArray(31)
for (i in 2..30) {
var x = i
var mask = 0
var ok = true
for (j in primes.indices) {
var cnt = 0
while (x % primes[j] == 0) {
x /= primes[j]
cnt++
}
if (cnt > 1) ok = false
if (cnt > 0) mask = mask or (1 shl j)
}
if (ok) numMask[i] = mask
}
val freq = IntArray(31)
for (x in nums) freq[x]++
val dp = LongArray(1 shl 10)
dp[0] = 1L
for (i in 2..30) {
if (numMask[i] == 0 || freq[i] == 0) continue
for (mask in (1 shl 10) - 1 downTo 0) {
if ((mask and numMask[i]) == 0) {
dp[mask or numMask[i]] = (dp[mask or numMask[i]] + dp[mask] * freq[i]) % MOD
}
}
}
var ans = 0L
for (mask in 1 until (1 shl 10)) ans = (ans + dp[mask]) % MOD
val ones = freq[1]
var pow2 = 1L
repeat(ones) { pow2 = pow2 * 2 % MOD }
ans = ans * pow2 % MOD
ans = (ans + pow2 - 1 + MOD) % MOD
return ans.toInt()
}
}
Python
class Solution:
def countSquareFreeSubsets(self, nums: list[int]) -> int:
MOD = 10**9 + 7
primes = [2,3,5,7,11,13,17,19,23,29]
num_mask = [0] * 31
for i in range(2, 31):
x, mask, ok = i, 0, True
for j, p in enumerate(primes):
cnt = 0
while x % p == 0:
x //= p
cnt += 1
if cnt > 1:
ok = False
if cnt:
mask |= 1 << j
if ok:
num_mask[i] = mask
freq = [0] * 31
for x in nums:
freq[x] += 1
dp = [1] + [0] * ((1 << 10) - 1)
for i in range(2, 31):
if not num_mask[i] or not freq[i]:
continue
for mask in range((1 << 10) - 1, -1, -1):
if mask & num_mask[i] == 0:
dp[mask | num_mask[i]] = (dp[mask | num_mask[i]] + dp[mask] * freq[i]) % MOD
ans = sum(dp[1:]) % MOD
ones = freq[1]
pow2 = pow(2, ones, MOD)
ans = ans * pow2 % MOD
ans = (ans + pow2 - 1 + MOD) % MOD
return ans
Rust
impl Solution {
pub fn count_square_free_subsets(nums: Vec<i32>) -> i32 {
const MOD: i64 = 1_000_000_007;
let primes = [2,3,5,7,11,13,17,19,23,29];
let mut num_mask = [0; 31];
for i in 2..=30 {
let mut x = i;
let mut mask = 0;
let mut ok = true;
for (j, &p) in primes.iter().enumerate() {
let mut cnt = 0;
while x % p == 0 {
x /= p;
cnt += 1;
}
if cnt > 1 { ok = false; }
if cnt > 0 { mask |= 1 << j; }
}
if ok { num_mask[i as usize] = mask; }
}
let mut freq = [0; 31];
for &x in &nums { freq[x as usize] += 1; }
let mut dp = vec![0i64; 1 << 10];
dp[0] = 1;
for i in 2..=30 {
if num_mask[i] == 0 || freq[i] == 0 { continue; }
for mask in (0..(1 << 10)).rev() {
if mask & num_mask[i] == 0 {
dp[mask | num_mask[i]] = (dp[mask | num_mask[i]] + dp[mask] * freq[i] as i64) % MOD;
}
}
}
let mut ans = 0i64;
for mask in 1..(1 << 10) { ans = (ans + dp[mask]) % MOD; }
let ones = freq[1];
let mut pow2 = 1i64;
for _ in 0..ones { pow2 = pow2 * 2 % MOD; }
ans = ans * pow2 % MOD;
ans = (ans + pow2 - 1 + MOD) % MOD;
ans as i32
}
}
TypeScript
class Solution {
countSquareFreeSubsets(nums: number[]): number {
const MOD = 1e9 + 7
const primes = [2,3,5,7,11,13,17,19,23,29]
const numMask = Array(31).fill(0)
for (let i = 2; i <= 30; ++i) {
let x = i, mask = 0, ok = true
for (let j = 0; j < primes.length; ++j) {
let cnt = 0
while (x % primes[j] === 0) {
x /= primes[j]
cnt++
}
if (cnt > 1) ok = false
if (cnt) mask |= (1 << j)
}
if (ok) numMask[i] = mask
}
const freq = Array(31).fill(0)
for (const x of nums) freq[x]++
const dp = Array(1 << 10).fill(0)
dp[0] = 1
for (let i = 2; i <= 30; ++i) {
if (!numMask[i] || !freq[i]) continue
for (let mask = (1 << 10) - 1; mask >= 0; --mask) {
if ((mask & numMask[i]) === 0) {
dp[mask | numMask[i]] = (dp[mask | numMask[i]] + dp[mask] * freq[i]) % MOD
}
}
}
let ans = 0
for (let mask = 1; mask < (1 << 10); ++mask) ans = (ans + dp[mask]) % MOD
const ones = freq[1]
let pow2 = 1
for (let i = 0; i < ones; ++i) pow2 = pow2 * 2 % MOD
ans = ans * pow2 % MOD
ans = (ans + pow2 - 1 + MOD) % MOD
return ans
}
}
Complexity
- ⏰ Time complexity:
O(n * 2^p)where n is the length of nums and p=10 (number of primes up to 30), since for each number we update all masks. - 🧺 Space complexity:
O(2^p)for the DP array and O(1) for other structures.