Welcome to Subscribe On Youtube
2572. Count the Number of SquareFree Subsets
Description
You are given a positive integer 0indexed array nums
.
A subset of the array nums
is squarefree if the product of its elements is a squarefree integer.
A squarefree integer is an integer that is divisible by no square number other than 1
.
Return the number of squarefree nonempty subsets of the array nums. Since the answer may be too large, return it modulo 10^{9} + 7
.
A nonempty 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.
Example 1:
Input: nums = [3,4,4,5] Output: 3 Explanation: There are 3 squarefree subsets in this example:  The subset consisting of the 0^{th} element [3]. The product of its elements is 3, which is a squarefree integer.  The subset consisting of the 3^{rd} element [5]. The product of its elements is 5, which is a squarefree integer.  The subset consisting of 0^{th} and 3^{rd} elements [3,5]. The product of its elements is 15, which is a squarefree integer. It can be proven that there are no more than 3 squarefree subsets in the given array.
Example 2:
Input: nums = [1] Output: 1 Explanation: There is 1 squarefree subset in this example:  The subset consisting of the 0^{th} element [1]. The product of its elements is 1, which is a squarefree integer. It can be proven that there is no more than 1 squarefree subset in the given array.
Constraints:
1 <= nums.length <= 1000
1 <= nums[i] <= 30
Solutions
Solution 1: State Compression Dynamic Programming
Note that in the problem, the range of $nums[i]$ is $[1, 30]$. Therefore, we can preprocess all prime numbers less than or equal to $30$, which are $[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]$.
In the subset without square numbers, the product of all elements can be represented as the product of one or more distinct prime numbers, that is, each prime factor can appear at most once. Therefore, we can use a binary number to represent the prime factors in a subset, where the $i$th bit of the binary number indicates whether the prime number $primes[i]$ appears in the subset.
We can use the method of state compression dynamic programming to solve this problem. Let $f[i]$ represent the number of schemes where the product of prime factors in the subset represented by the binary number $i$ is the product of one or more distinct prime numbers. Initially, $f[0]=1$.
We enumerate a number $x$ in the range $[2,..30]$. If $x$ is not in $nums$, or $x$ is a multiple of $4, 9, 25$, then we can skip it directly. Otherwise, we can represent the prime factors of $x$ with a binary number $mask$. Then we enumerate the current state $state$ from large to small. If the result of $state$ and $mask$ bitwise AND is $mask$, then we can transition from state $f[state \oplus mask]$ to state $f[state]$, the transition equation is $f[state] = f[state] + cnt[x] \times f[state \oplus mask]$, where $cnt[x]$ represents the number of times $x$ appears in $nums$.
Note that we did not start enumerating from the number $1$, because we can choose any number of number $1$ and add it to the subset without square numbers. Or we can only choose any number of number $1$ and not add it to the subset without square numbers. Both situations are legal. So the answer is $(\sum_{i=0}^{2^{10}1} f[i])  1$.
The time complexity is $O(n + C \times M)$, and the space complexity is $O(M)$. Where $n$ is the length of $nums$; and $C$ and $M$ are the range of $nums[i]$ and the number of states in the problem, in this problem, $C=30$, $M=2^{10}$.

class Solution { public int squareFreeSubsets(int[] nums) { int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; int[] cnt = new int[31]; for (int x : nums) { ++cnt[x]; } final int mod = (int) 1e9 + 7; int n = primes.length; long[] f = new long[1 << n]; f[0] = 1; for (int i = 0; i < cnt[1]; ++i) { f[0] = (f[0] * 2) % mod; } for (int x = 2; x < 31; ++x) { if (cnt[x] == 0  x % 4 == 0  x % 9 == 0  x % 25 == 0) { continue; } int mask = 0; for (int i = 0; i < n; ++i) { if (x % primes[i] == 0) { mask = 1 << i; } } for (int state = (1 << n)  1; state > 0; state) { if ((state & mask) == mask) { f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod; } } } long ans = 0; for (int i = 0; i < 1 << n; ++i) { ans = (ans + f[i]) % mod; } ans = 1; return (int) ans; } }

class Solution { public: int squareFreeSubsets(vector<int>& nums) { int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}; int cnt[31]{}; for (int& x : nums) { ++cnt[x]; } int n = 10; const int mod = 1e9 + 7; vector<long long> f(1 << n); f[0] = 1; for (int i = 0; i < cnt[1]; ++i) { f[0] = f[0] * 2 % mod; } for (int x = 2; x < 31; ++x) { if (cnt[x] == 0  x % 4 == 0  x % 9 == 0  x % 25 == 0) { continue; } int mask = 0; for (int i = 0; i < n; ++i) { if (x % primes[i] == 0) { mask = 1 << i; } } for (int state = (1 << n)  1; state; state) { if ((state & mask) == mask) { f[state] = (f[state] + 1LL * cnt[x] * f[state ^ mask]) % mod; } } } long long ans = 1; for (int i = 0; i < 1 << n; ++i) { ans = (ans + f[i]) % mod; } return ans; } };

class Solution: def squareFreeSubsets(self, nums: List[int]) > int: primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] cnt = Counter(nums) mod = 10**9 + 7 n = len(primes) f = [0] * (1 << n) f[0] = pow(2, cnt[1]) for x in range(2, 31): if cnt[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0: continue mask = 0 for i, p in enumerate(primes): if x % p == 0: mask = 1 << i for state in range((1 << n)  1, 0, 1): if state & mask == mask: f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod return sum(v for v in f) % mod  1

func squareFreeSubsets(nums []int) (ans int) { primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29} cnt := [31]int{} for _, x := range nums { cnt[x]++ } const mod int = 1e9 + 7 n := 10 f := make([]int, 1<<n) f[0] = 1 for i := 0; i < cnt[1]; i++ { f[0] = f[0] * 2 % mod } for x := 2; x < 31; x++ { if cnt[x] == 0  x%4 == 0  x%9 == 0  x%25 == 0 { continue } mask := 0 for i, p := range primes { if x%p == 0 { mask = 1 << i } } for state := 1<<n  1; state > 0; state { if state&mask == mask { f[state] = (f[state] + f[state^mask]*cnt[x]) % mod } } } ans = 1 for _, v := range f { ans = (ans + v) % mod } return }

function squareFreeSubsets(nums: number[]): number { const primes: number[] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]; const cnt: number[] = Array(31).fill(0); for (const x of nums) { ++cnt[x]; } const mod: number = Math.pow(10, 9) + 7; const n: number = primes.length; const f: number[] = Array(1 << n).fill(0); f[0] = 1; for (let i = 0; i < cnt[1]; ++i) { f[0] = (f[0] * 2) % mod; } for (let x = 2; x < 31; ++x) { if (cnt[x] === 0  x % 4 === 0  x % 9 === 0  x % 25 === 0) { continue; } let mask: number = 0; for (let i = 0; i < n; ++i) { if (x % primes[i] === 0) { mask = 1 << i; } } for (let state = (1 << n)  1; state > 0; state) { if ((state & mask) === mask) { f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod; } } } let ans: number = 0; for (let i = 0; i < 1 << n; ++i) { ans = (ans + f[i]) % mod; } ans = 1; return ans >= 0 ? ans : ans + mod; }