Count The Number Of Square Free Subsets - Leetcode Solution

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.

1