Problem Description

You are given a positive integer array nums (0-indexed).

A square-free integer is an integer that is not divisible by any perfect square other than 1. In other words, it cannot be divided by numbers like 4, 9, 16, 25, etc.

A square-free subset is a subset of nums where the product of all its elements results in a square-free integer.

Your task is to find the total number of non-empty square-free subsets that can be formed from the array nums. Since the answer can be very large, return it modulo 10^9 + 7.

Key points to understand:

• A subset is formed by selecting some (possibly all, but not none) elements from nums
• Two subsets are considered different if they are formed by selecting different indices from the array
• The product of elements in a valid subset must be square-free
• You need to count all possible non-empty subsets that satisfy the square-free condition

For example, if we have a subset {2, 3, 5}, their product is 2 × 3 × 5 = 30, which is square-free since it's not divisible by any perfect square except 1. However, if we have {2, 2}, their product is 4, which is not square-free since it's divisible by the perfect square 4.

Intuition

Let's think about what makes a number square-free. A number is square-free if no prime appears more than once in its prime factorization. For example, 30 = 2 × 3 × 5 is square-free, but 12 = 2² × 3 is not because 2 appears twice.

Since the problem limits nums[i] to the range [1, 30], we can identify all prime numbers up to 30: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]. This gives us only 10 primes to work with.

The key insight is that for a product of multiple numbers to be square-free, each prime factor across all numbers can appear at most once in total. If we multiply two numbers that share a common prime factor, the product won't be square-free. For instance, multiplying 6 = 2 × 3 with 10 = 2 × 5 gives 60 = 2² × 3 × 5, which isn't square-free because 2 appears twice.

This constraint suggests we can represent which primes are "used" in our subset using a bitmask. With 10 primes, we need 10 bits, where bit i indicates whether the i-th prime is present in our product. This gives us 2^10 = 1024 possible states.

We can use dynamic programming where f[state] represents the number of ways to form subsets whose product has exactly the prime factors indicated by the bitmask state.

For each number x in the range [2, 30]:

• First, check if x itself is square-free (skip numbers like 4, 9, 25 which contain squared primes)
• Find which primes divide x and represent this as a bitmask
• For each existing state, if we can add x to subsets with that state (meaning no prime conflicts), we update the count

The number 1 is special - it doesn't contribute any prime factors, so we can include any number of 1's in any subset. If there are cnt[1] ones in the array, we can choose to include 0, 1, 2, ..., or all of them, giving us 2^cnt[1] choices for each valid subset configuration.

Learn more about Math, Dynamic Programming and Bitmask patterns.

Solution Approach

We implement the solution using state compression dynamic programming with bitmasks to track which prime factors are used.

Step 1: Preprocessing

• Define the list of primes up to 30: primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
• Count the frequency of each number in nums using Counter
• Initialize DP array f of size 2^10 where f[state] represents the number of ways to form subsets with prime factors represented by the bitmask state

Step 2: Handle the special case of 1

• Set f[0] = 2^cnt[1] because we can choose any subset of 1's (including empty subset)
• The number 1 has no prime factors, so it only affects the empty state

Step 3: Process each number from 2 to 30

For each number x in range [2, 30]:

1. Skip invalid numbers:

   • Skip if cnt[x] == 0 (number not in array)
   • Skip if x is divisible by perfect squares: x % 4 == 0 or x % 9 == 0 or x % 25 == 0

2. Calculate the prime mask for x:

   mask = 0
   for i, p in enumerate(primes):
       if x % p == 0:
           mask |= 1 << i

   This creates a bitmask where bit i is set if prime primes[i] divides x.

3. Update states in reverse order:

   for state in range((1 << n) - 1, 0, -1):
       if state & mask == mask:
           f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod

   • We iterate states from large to small to avoid using updated values in the same iteration
   • Condition state & mask == mask checks if state contains all primes in mask
   • state ^ mask removes the primes of x from state, giving us the previous state
   • We multiply by cnt[x] because we can choose any occurrence of x from the array

Step 4: Calculate the final answer

• Sum all values in f: this gives the total number of square-free subsets (including empty subset from choosing no elements except possibly 1's)
• Subtract 1 to exclude the empty subset: sum(f) % mod - 1

The time complexity is O(n + C × M) where n is the length of nums, C = 30 is the range of values, and M = 2^10 is the number of states. The space complexity is O(M) for the DP array.

Example Walkthrough

Let's walk through a small example with nums = [2, 3, 6].

Step 1: Identify key information

• Primes up to 30: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
• Count frequencies: cnt[2] = 1, cnt[3] = 1, cnt[6] = 1
• We need 10 bits for our bitmask (one for each prime)

Step 2: Initialize DP array

• f[0] = 1 (since there are no 1's in our array, we start with 1 way to form empty product)
• All other states start at 0

Step 3: Process each number

Processing number 2:

• 2 is prime and square-free
• Prime mask for 2: mask = 0b0000000001 (only bit 0 set, representing prime 2)
• Update states in reverse:
  • For state = 0b0000000001 (has prime 2):
    • Check: state & mask == mask? Yes (0b0000000001 & 0b0000000001 = 0b0000000001)
    • Previous state: state ^ mask = 0b0000000000
    • Update: f[0b0000000001] = f[0b0000000001] + 1 * f[0b0000000000] = 0 + 1 * 1 = 1

Processing number 3:

• 3 is prime and square-free
• Prime mask for 3: mask = 0b0000000010 (bit 1 set, representing prime 3)
• Update states in reverse:
  • For state = 0b0000000011 (has primes 2 and 3):
    • Check: state & mask == mask? Yes
    • Previous state: state ^ mask = 0b0000000001
    • Update: f[0b0000000011] = 0 + 1 * f[0b0000000001] = 0 + 1 * 1 = 1
  • For state = 0b0000000010 (has prime 3):
    • Check: state & mask == mask? Yes
    • Previous state: state ^ mask = 0b0000000000
    • Update: f[0b0000000010] = 0 + 1 * f[0b0000000000] = 0 + 1 * 1 = 1

Processing number 6:

• 6 = 2 × 3, so it's square-free
• Prime mask for 6: mask = 0b0000000011 (bits 0 and 1 set, for primes 2 and 3)
• Update states in reverse:
  • For state = 0b0000000011 (has primes 2 and 3):
    • Check: state & mask == mask? Yes
    • Previous state: state ^ mask = 0b0000000000
    • Update: f[0b0000000011] = 1 + 1 * f[0b0000000000] = 1 + 1 * 1 = 2

Step 4: Calculate final answer

Current DP state:

• f[0b0000000000] = 1 (empty subset)
• f[0b0000000001] = 1 (subset {2}, product = 2)
• f[0b0000000010] = 1 (subset {3}, product = 3)
• f[0b0000000011] = 2 (subsets {2,3} with product = 6, and {6} with product = 6)

Total = 1 + 1 + 1 + 2 = 5 Answer = 5 - 1 = 4 (excluding empty subset)

The 4 valid square-free subsets are:

1. {2} → product = 2 (square-free)
2. {3} → product = 3 (square-free)
3. {6} → product = 6 (square-free)
4. {2, 3} → product = 6 (square-free)

Note that {2, 6} would give product = 12 = 2² × 3 (not square-free), and {3, 6} would give product = 18 = 2 × 3² (not square-free), so these are correctly not counted by our algorithm.

Solution Implementation

Time and Space Complexity

Time Complexity: O(2^n + 31 * 2^n) where n = 10 (number of primes)

• Creating the counter takes O(m) where m is the length of the input array nums
• Initializing array f takes O(2^n) where n = 10
• The main loop iterates through numbers 2 to 30 (29 iterations)
• For each valid number x, we check divisibility by 10 primes: O(10)
• For each valid number, we iterate through all states from 2^n - 1 to 1: O(2^n)
• Inside the inner loop, we perform constant time operations
• Total: O(m + 2^n + 29 * (10 + 2^n)) = O(m + 2^n * 29) = O(m + 2^10 * 29)
• Since 2^10 = 1024 and this dominates for typical input sizes, the complexity simplifies to O(2^n) where n = 10

Space Complexity: O(2^n + m) where n = 10 and m is the number of unique elements in nums

• The f array stores 2^n = 2^10 = 1024 elements: O(2^n)
• The counter stores at most m unique elements from the input: O(m)
• The primes list is constant size: O(1)
• Other variables use constant space: O(1)
• Total: O(2^n + m) = O(2^10 + m) = O(1024 + m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Number 1

Pitfall: A common mistake is treating 1 like any other number in the DP update loop. Since 1 has no prime factors, it doesn't affect which primes are used in the product, but it does affect the count of valid subsets.

Wrong approach:

# Processing 1 in the main loop like other numbers
for number in range(1, 31):  # Starting from 1 instead of 2
    if number == 1:
        # Incorrect: trying to update states with mask = 0
        for state in range((1 << num_primes) - 1, 0, -1):
            dp[state] = (dp[state] + frequency[1] * dp[state]) % MOD

Correct approach:

# Handle 1 separately before the main loop
dp[0] = pow(2, frequency[1], MOD)  # Can choose any subset of 1's
# Then process numbers from 2 to 30
for number in range(2, 31):
    # ... rest of the logic

2. Not Checking for Perfect Square Divisors Correctly

Pitfall: Only checking if a number is a perfect square itself, rather than checking if it's divisible by any perfect square.

Wrong approach:

# Only checking if the number itself is a perfect square
import math
if int(math.sqrt(number))**2 == number:
    continue

Correct approach:

# Check divisibility by all relevant perfect squares
if number % 4 == 0 or number % 9 == 0 or number % 25 == 0:
    continue

3. Incorrect DP State Update Order

Pitfall: Updating states in ascending order can cause using already-updated values in the same iteration, leading to incorrect counting.

Wrong approach:

# Iterating states from small to large
for state in range(1, 1 << num_primes):
    if state & prime_mask == prime_mask:
        dp[state] = (dp[state] + frequency[number] * dp[state ^ prime_mask]) % MOD

Correct approach:

# Iterate from largest state to smallest
for state in range((1 << num_primes) - 1, 0, -1):
    if state & prime_mask == prime_mask:
        dp[state] = (dp[state] + frequency[number] * dp[state ^ prime_mask]) % MOD

4. Forgetting to Subtract 1 for Empty Subset

Pitfall: The problem asks for non-empty subsets, but the DP counts all subsets including the empty one.

Wrong approach:

# Returning the sum directly
return sum(dp) % MOD

Correct approach:

# Subtract 1 to exclude the empty subset
total = sum(dp) % MOD
return total - 1

5. Incorrect Modulo Operation

Pitfall: Forgetting to apply modulo at each step or applying it incorrectly when subtracting.

Wrong approach:

# Not handling potential negative result after subtraction
return (sum(dp) - 1) % MOD  # Can be negative if sum(dp) % MOD == 0

Correct approach:

# Ensure non-negative result
total = sum(dp) % MOD
return (total - 1 + MOD) % MOD  # Adding MOD ensures non-negative
# Or simply:
return total - 1  # Since total >= 1 after modulo