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.
In this approach, we use bitmasks to iterate over all possible subsets of the array. For each subset, we calculate the product and check if the product is square-free. To determine if a number is square-free, we can use its prime factorization and ensure that no prime number has an exponent greater than 1 in the factorization.
The function is_square_free checks if a number is square-free by verifying that it is not divisible by any square numbers greater than 1. The main function, count_square_free_subsets, generates all subset combinations using bitmasks, calculates their product, and checks for the square-free condition.
Time Complexity: O(2^n * sqrt(p)) where n is the length of the array and p is the maximum product of the subset elements.
Space Complexity: O(1) ignoring the space used by recursive stack calls.
This approach leverages dynamic programming to efficiently count square-free subsets. By representing numbers with their prime factor bitmask, we ensure that the product is square-free by checking that no bit is set twice in the combined bitmask representation.
In the C++ solution, the numbers are directly indexed into an array of precomputed prime masks. The DP array dp keeps track of ways to form square-free subsets by checking and setting necessary prime factor bits.
C++
JavaScript
Time Complexity: O(n * 2^m) where n is the length of the array and m is the number of distinct prime factors considered.
Space Complexity: O(2^20) due to the DP array used for bitmask processing.
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}.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Bitmask and Prime Factorization | Time Complexity: O(2^n * sqrt(p)) where n is the length of the array and p is the maximum product of the subset elements. Space Complexity: O(1) ignoring the space used by recursive stack calls. |
| Dynamic Programming with Bitwise Representation | Time Complexity: O(n * 2^m) where n is the length of the array and m is the number of distinct prime factors considered. Space Complexity: O(2^20) due to the DP array used for bitmask processing. |
| State Compression 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 |
2572. Count the Number of Square-Free Subsets | Leetcode • A Code Daily! • 3,736 views views
Watch 5 more video solutions →Practice Count the Number of Square-Free Subsets with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor