Watch 6 video solutions for Count the Number of Square-Free Subsets, a medium level problem involving Array, Math, Dynamic Programming. This walkthrough by A Code Daily! has 3,736 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 109 + 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.
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] <= 30Problem Overview: Given an integer array nums, count the number of non-empty subsets whose product is square-free. A square-free number has no prime factor repeated (no factor like p²). Since values are limited to 1..30, you can track prime factors using bitmasks and combine subsets without introducing duplicate primes.
Approach 1: Bitmask and Prime Factorization (O(n * 2^10) time, O(2^10) space)
Each number from 2 to 30 can be represented by a bitmask of its prime factors among the first ten primes (2–29). Precompute masks and discard numbers containing squared prime factors (like 4, 8, 9, 12). Maintain a DP array where dp[mask] counts subsets whose combined prime factors equal that mask. Iterate through the array, and for each valid number mask, update states in reverse so overlapping primes are avoided using (mask & newMask) == 0. Numbers equal to 1 contribute multiplicatively because they do not affect the mask. This technique combines bitmasking with prime factorization to efficiently track valid products.
Approach 2: Dynamic Programming with Bitwise Representation (O(n * 2^10) time, O(2^10) space)
This approach frames the problem purely as dynamic programming. Precompute valid prime masks for each possible value. Then iterate through the array and update DP states that represent which primes are already used in the subset product. For each state, attempt to merge the current number's mask if no prime conflict occurs. Because only 10 primes exist in the range, the DP state space is limited to 2^10. This keeps the algorithm fast even for larger arrays and avoids explicit subset enumeration.
The key observation: a subset is square-free if and only if no prime factor appears more than once across the product. Bitmasks encode this constraint directly, allowing constant-time conflict checks using bitwise AND. The small constraint on numbers makes this far more efficient than brute-force subset generation.
Recommended for interviews: Use the bitmask + DP approach. Interviewers expect recognition that the value range is small and prime factors can be encoded into a 10-bit mask. Brute force over all subsets shows baseline reasoning, but the optimal solution demonstrates strong understanding of array processing, bit manipulation, and state-compressed dynamic programming.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Bitmask and Prime Factorization | O(n * 2^10) | O(2^10) | Best general solution when numbers are limited to 1..30 and prime factors can be encoded as bitmasks |
| Dynamic Programming with Bitwise Representation | O(n * 2^10) | O(2^10) | Useful when implementing state-compressed DP and combining subset states efficiently |