Skip to main content
Talentd

Count the Number of Square-Free Subsets - Solution & Explanation

MediumArrayMathDynamic ProgrammingBit Manipulation20 min readAsked at: Google, Medianet
Practice this problem

Problem Statement

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 <= 1000
  • 1 <= nums[i] <= 30

Approach Overview

Problem 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 1: Bitmask and Prime Factorization

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.

Code

PythonJava

Python

Java

Complexity

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.

Try this approach in the editor →

Approach 2: Dynamic Programming with Bitwise Representation

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.

Code

C++JavaScript

C++

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: 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}.

Similar problems:

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Bitmask and Prime FactorizationO(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 RepresentationO(n * 2^10)O(2^10)Useful when implementing state-compressed DP and combining subset states efficiently

Video Solution

2572. Count the Number of Square-Free Subsets | Leetcode • A Code Daily! • 3,769 views views

Watch 6 more video solutions →

Frequently Asked Questions

Is Count the Number of Square-Free Subsets easy or hard?
The problem is rated Medium on LeetCode but feels closer to Medium–Hard for many candidates. The challenge lies in recognizing that the limited number range allows encoding prime factors into a bitmask and solving the subset counting with dynamic programming.
Count the Number of Square-Free Subsets Python/Java solution
Python and Java implementations typically precompute prime masks for numbers from 2 to 30 and then update a DP array of size 1024. Each iteration merges compatible masks using bitwise AND checks to prevent repeated prime factors.
How to solve Count the Number of Square-Free Subsets in O(n)?
Pure O(n) is not achievable because subset combinations must be tracked. The closest efficient solution is O(n * 2^10) using bitmask dynamic programming. Since 2^10 is only 1024, this behaves nearly linear for practical constraints while still guaranteeing correctness.
What is the best approach for Count the Number of Square-Free Subsets?
The most efficient approach uses bitmasking with dynamic programming. Each number is represented by a bitmask of its prime factors, and DP states track which primes are already used in the subset. This avoids duplicate prime factors and ensures the product remains square-free. The algorithm runs in O(n * 2^10) time with O(2^10) space.
Is Count the Number of Square-Free Subsets asked at Google/Amazon/Meta?
Square-free subset problems and bitmask DP questions commonly appear in interviews at companies like Google, Amazon, and Meta. They test understanding of prime factorization, state compression, and dynamic programming with bitwise operations.
What data structure is used in Count the Number of Square-Free Subsets?
The core structure is a dynamic programming array indexed by bitmask states. Each bit represents whether a specific prime factor is already used in the subset product. Bitwise operations quickly check conflicts and merge states.
What is the time complexity of Count the Number of Square-Free Subsets?
The optimal solution runs in O(n * 2^10) time. There are at most 10 relevant primes for numbers up to 30, so the DP state space contains 1024 masks. For each number in the array, the algorithm iterates through possible masks and updates valid subset states.

Ready to solve this problem?

Practice Count the Number of Square-Free Subsets with our built-in code editor and test cases.

Practice on FleetCode
Previous

Distinct Prime Factors of Product of Array