## Similar Problems

Similar Problems not available

# Count The Number Of Square Free Subsets - Leetcode Solution

## Companies:

LeetCode: Count The Number Of Square Free Subsets Leetcode Solution

Difficulty: Medium

Topics: math dynamic-programming bit-manipulation array

Problem Statement: Given an array nums of unique integers, return the number of all possible square-free subsets of nums. A subset is square-free if every element not equal to 1 cannot be divisible by any perfect square (including 1).

Example 1: Input: nums = [4,2,3,1,5] Output: 20 Explanation: The square-free subsets of the array are: [1], [2], [3], [5], [1,2], [1,3], [1,5], [2,5], [3,5], [1,2,5], [1,3,5], [2,3,5], [3,2,5], [1,3,2,5], [4], [4,2], [4,3], [4,5], [4,2,3], [4,3,5]. The sum is 20.

Solution: The idea to solve this problem is to use bit manipulation and prime factorization. First, we will create a mask for each element in the input array by iterating through the array and finding its prime factors. For example, the mask for 4 will be 2^2, and for 5 it will be 5^1.

Next, we will generate all possible subsets of the input array using bit manipulation. For every subset, we will check if it is a square-free subset or not. To check if a subset is square-free, we will check if the product of its mask is a square number or not. If the product is a square number, then the subset is not square-free.

We can check if a number is a square number by checking if the square root of the number is an integer or not. We can also use the fact that the square root of a number can be written as a product of its prime factors, and if the exponent of any prime factor is odd, then the number is a perfect square.

Finally, we will count the number of square-free subsets and return the count.

Here's the code implementation:

```
class Solution {
public:
int countSquareFreeSubsets(vector<int>& nums) {
int n = nums.size();
vector<int> masks(n);
for (int i = 0; i < n; i++) {
masks[i] = getMask(nums[i]);
}
int ans = 0;
for (int i = 1; i < (1 << n); i++) {
if (isSquareFree(i, masks)) {
ans++;
}
}
return ans;
}
int getMask(int x) {
int mask = 1;
for (int i = 2; i * i <= x; i++) {
int cnt = 0;
while (x % i == 0) {
x /= i;
cnt++;
}
if (cnt % 2 != 0) {
mask *= i;
}
}
if (x > 1) {
mask *= x;
}
return mask;
}
bool isSquareFree(int subset, vector<int>& masks) {
int mask = 1;
for (int i = 0; i < masks.size(); i++) {
if (subset & (1 << i)) {
mask *= masks[i];
}
}
int sqrtMask = sqrt(mask);
return sqrtMask * sqrtMask != mask;
}
};
```

Time Complexity: The time complexity of this solution is O(3^n). The algorithm generates all subsets of the input array, which takes O(2^n) time, and for each subset, it calculates the product of its mask and checks if it is square-free or not, which takes O(n) time. So, the overall time complexity is O(3^n).

Space Complexity: The space complexity of this algorithm is O(n). We are using an array to store the mask for each element in the input array, which takes O(n) space.

## Count The Number Of Square Free Subsets Solution Code

`1`