Scale Engineer

Count the Number of Square-Free Subsets

Med
#2352Time: O(N + 2^U), where `N` is the length of `nums` and `U` is the number of unique square-free numbers present in `nums` (`U <= 18`). The `O(N)` is for preprocessing `nums`. The `2^U` comes from the binary recursion tree. Since `U` is small, this approach is feasible and can pass.Space: O(U), where `U` is the number of unique square-free numbers in `nums`. This space is used by the recursion stack. Since `U` is at most 18, this is effectively constant space.1 company
Patterns
MathDynamic ProgrammingBit ManipulationBitmask
Data structures
Array
Companies
Media.net

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a recursive backtracking algorithm. We first process the input array to count the frequencies of each number and filter out non-square-free numbers. The core of the approach is a recursive function that explores the choices of including or not including each unique square-free number to form a valid subset. A subset is valid if the prime factors of the newly added number do not overlap with the prime factors of the numbers already in the subset. We use a bitmask to efficiently track the set of prime factors used.

Algorithm

  1. Pre-process the input nums to count the frequency of each number.
  2. Identify the unique square-free numbers greater than 1 present in nums.
  3. Implement a recursive function, say solve(index, mask), where index refers to the current unique square-free number being considered, and mask is a bitmask representing the prime factors used by the subset constructed so far.
  4. In the recursive function, for each number, explore two possibilities: a. Exclude the number: Make a recursive call solve(index + 1, mask). b. Include the number: If its prime factor mask does not conflict with the current mask, make a recursive call solve(index + 1, new_mask) and multiply the result by the frequency of the number. This accounts for the different ways to choose this number if it appears multiple times.
  5. The base case for the recursion is when all unique numbers have been considered (index reaches the end), at which point we return 1 (representing one validly formed subset).
  6. Sum the results from the recursive calls to get the total count of square-free subsets formed from numbers greater than 1 (let's call this C').
  7. The number 1 can be part of any square-free subset. If there are k ones in nums, they can form 2^k subsets (including the empty one). The total number of square-free subsets is C' * 2^k.
  8. Subtract 1 from the total to exclude the overall empty subset and return the result modulo 10^9 + 7.

Walkthrough

First, we can simplify the problem. Any number in nums that is not square-free (i.e., divisible by 4, 9, 25, etc.) can never be part of a square-free subset, so we can ignore them. The number 1 is square-free and coprime with any other number, so it can be combined with any square-free subset. We can handle all occurrences of 1s at the end.

The problem then reduces to finding the number of square-free subsets of nums containing only square-free numbers greater than 1. A subset is square-free if and only if all its elements are square-free and pairwise coprime. This means their sets of prime factors must be disjoint.

We can represent the set of prime factors of a number using a bitmask. Since all numbers are at most 30, we only need to consider primes up to 30, which are {2, 3, 5, 7, 11, 13, 17, 19, 23, 29} (10 primes).

The algorithm proceeds as follows:

  • Count the frequency of each number in nums.
  • Let count1 be the frequency of the number 1.
  • Create a list of unique square-free numbers > 1 present in nums.
  • A recursive function solve(idx, mask) is defined, which calculates the number of valid subsets using numbers from unique_sf_nums[idx:], given that the primes represented by mask are already used.
  • In solve(idx, mask), we have two choices for unique_sf_nums[idx]:
    1. Don't include it: Recursively call solve(idx + 1, mask).
    2. Include it: This is possible only if its prime factor mask doesn't overlap with mask. If so, we add count(num) * solve(idx + 1, new_mask) to the result, where count(num) is the frequency of the number.
  • The base case for the recursion is when idx reaches the end of the list, in which case we return 1 (for the one valid subset formed).
  • The initial call is solve(0, 0). Let the result be C'. This is the number of square-free subsets (including empty) from numbers > 1.
  • The total number of subsets is C' * 2^count1. The final answer is this value minus 1 (to exclude the all-empty subset).
class Solution {    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};    int[] masks;    long MOD = 1_000_000_007;    List<Integer> uniqueSfNums;    int[] counts;     public int squareFreeSubsets(int[] nums) {        counts = new int[31];        for (int num : nums) {            counts[num]++;        }         masks = new int[31];        for (int i = 2; i <= 30; i++) {            masks[i] = getMask(i);        }         uniqueSfNums = new ArrayList<>();        for (int i = 2; i <= 30; i++) {            if (counts[i] > 0 && masks[i] != -1) {                uniqueSfNums.add(i);            }        }         long countGt1 = solve(0, 0);        long count1 = counts[1];        long total = (countGt1 * power(2, count1)) % MOD;        return (int)((total - 1 + MOD) % MOD);    }     private long solve(int idx, int mask) {        if (idx == uniqueSfNums.size()) {            return 1;        }         // Option 1: Don't include uniqueSfNums[idx]        long res = solve(idx + 1, mask);         // Option 2: Include uniqueSfNums[idx]        int num = uniqueSfNums.get(idx);        int numMask = masks[num];        if ((mask & numMask) == 0) {            long ways = (counts[num] * solve(idx + 1, mask | numMask)) % MOD;            res = (res + ways) % MOD;        }         return res;    }     private int getMask(int n) {        int mask = 0;        for (int i = 0; i < primes.length; i++) {            int p = primes[i];            if (n % (p * p) == 0) return -1; // Not square-free            if (n % p == 0) {                mask |= (1 << i);            }        }        return mask;    }     private long power(long base, long exp) {        long res = 1;        base %= MOD;        while (exp > 0) {            if (exp % 2 == 1) res = (res * base) % MOD;            base = (base * base) % MOD;            exp /= 2;        }        return res;    }}

Complexity

Time

O(N + 2^U), where `N` is the length of `nums` and `U` is the number of unique square-free numbers present in `nums` (`U <= 18`). The `O(N)` is for preprocessing `nums`. The `2^U` comes from the binary recursion tree. Since `U` is small, this approach is feasible and can pass.

Space

O(U), where `U` is the number of unique square-free numbers in `nums`. This space is used by the recursion stack. Since `U` is at most 18, this is effectively constant space.

Trade-offs

Pros

  • Conceptually straightforward recursive solution that directly models the decision process.

Cons

  • Highly inefficient due to re-computation of results for the same state (index and mask).

  • The time complexity is exponential in the number of unique square-free elements, which might be too slow if the number of such elements were larger.

Solutions

class Solution {public  int squareFreeSubsets(int[] nums) {    int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};    int[] cnt = new int[31];    for (int x : nums) {      ++cnt[x];    }    final int mod = (int)1 e9 + 7;    int n = primes.length;    long[] f = new long[1 << n];    f[0] = 1;    for (int i = 0; i < cnt[1]; ++i) {      f[0] = (f[0] * 2) % mod;    }    for (int x = 2; x < 31; ++x) {      if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {        continue;      }      int mask = 0;      for (int i = 0; i < n; ++i) {        if (x % primes[i] == 0) {          mask |= 1 << i;        }      }      for (int state = (1 << n) - 1; state > 0; --state) {        if ((state & mask) == mask) {          f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod;        }      }    }    long ans = 0;    for (int i = 0; i < 1 << n; ++i) {      ans = (ans + f[i]) % mod;    }    ans -= 1;    return (int)ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem