Count the Number of Square-Free Subsets

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

1
2
3
4
5
6
7


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

1
2
3
4
5


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 <= 1000
1 <= 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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52


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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


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()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


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
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40


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.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Bitmask Dynamic Programming#

Intuition#

Approach#

Code#

Complexity#