We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count the Number of Square-Free Subsets

Number: 2709

Difficulty: Medium

Paid? No

Companies: Google, Media.net

Problem Description

Given an array of positive integers (each between 1 and 30), count the number of non-empty subsets whose product is a square‐free integer. An integer is square‐free if it is not divisible by any square number other than 1. Return the answer modulo 10^9 + 7.

Key Insights

  • Only numbers that are square-free (i.e. they are not divisible by any square number > 1) can contribute to a valid product. In the range 1–30, some numbers (like 4, 8, 9, etc.) are not square-free.
  • The square-free condition implies that in the prime factorization of the product, no prime appears more than once.
  • Use a bitmask to represent which primes have been used so far. Each allowed number (except 1) can be pre-mapped to a bitmask representing its unique prime factors.
  • Since 1 is square-free and does not change the prime factors, its multiple occurrences can be handled separately using exponentiation.
  • A dynamic programming approach can be employed where the state is defined by the bitmask of primes already used, and transitions are done only when adding a new element does not conflict (i.e. share any prime factor).

Space and Time Complexity

Time Complexity: O(n * 2^P) where P is the number of primes used (≈ 10), so roughly O(1000 * 1024).
Space Complexity: O(2^P) for the DP table (≈ 1024 states).

Solution

We first precompute the allowed numbers (from 1 to 30) that are square-free and build their corresponding bitmask based on their prime factors (from the set [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]). We then count the frequencies of each number in the input array. The number 1 is handled separately since its inclusion does not affect the prime factorization (but it boosts the count by a multiplicative factor of 2 for each occurrence).

We use a DP approach where dp[mask] stores the number of ways to form a subset with prime factors represented by “mask”. We initialize dp[0] = 1 (the empty subset). For each allowed number (excluding 1) present in the input (considering its frequency), we iterate over current dp states. If the current state's mask has no overlapping primes with the candidate’s mask, we update the new state (combining the masks) by adding the product of ways with the frequency of that candidate.

Finally, after processing all numbers (except 1), we multiply the valid non-empty subsets (and include the dp[0] state for scenarios only containing ones) by 2^(count1) and subtract 1 to remove the empty subset.

This approach uses a combination of counting, bitmasking, and DP to ensure valid subset formation without repeated primes.

Code Solutions

# Python Solution

MOD = 10**9 + 7

def squareFreeSubsets(nums):
    from collections import Counter
    # Pre-defined primes that may appear in factorization of numbers up to 30.
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    
    # Map each number from 2 to 30 (only square-free ones) to its bitmask.
    num_to_mask = {}
    for num in range(2, 31):
        mask = 0
        valid = True  # flag to determine if the number is square-free
        for i, prime in enumerate(primes):
            count = 0
            temp = num
            while temp % prime == 0:
                count += 1
                temp //= prime
            # if the prime appears more than once, then the square divides the number.
            if count > 1:
                valid = False
                break
            if count == 1:
                mask |= (1 << i)
        if valid:
            num_to_mask[num] = mask

    # Count the frequency of each number in the array.
    freq = Counter(nums)
    # Count of 1's are handled separately.
    count1 = freq.get(1, 0)
    
    # Initialize the DP with state 0 (no prime factors picked).
    dp = {0: 1}
    
    # Iterate through candidate numbers (exclude 1 because they are handled specially).
    for num, mask in num_to_mask.items():
        if num not in freq:
            continue
        f = freq[num]  # frequency of the number 'num'
        # Make a copy of current dp states.
        for state, ways in list(dp.items()):
            # If current state and candidate mask do not share a common prime factor.
            if state & mask == 0:
                new_state = state | mask
                # Update the dp count for new_state by multiplying with the frequency of the candidate.
                dp[new_state] = (dp.get(new_state, 0) + ways * f) % MOD

    # Sum all dp states values. This sum includes the empty state.
    total = sum(dp.values()) % MOD
    # Multiply by all combinations contributed by ones (each one can double the number of subsets)
    total = total * pow(2, count1, MOD) % MOD
    # Subtract 1 for the empty subset.
    return (total - 1) % MOD

# Example usage:
print(squareFreeSubsets([3,4,4,5]))  # Expected output: 3
print(squareFreeSubsets([1]))        # Expected output: 1
← Back to All Questions