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

The Number of Good Subsets

Number: 2105

Difficulty: Hard

Paid? No

Companies: Media.net, Lowe's

Problem Description

Given an array of integers (each between 1 and 30), count the number of subsets (different by indices chosen) such that the product of the numbers in the subset can be represented as a product of one or more distinct prime numbers. In other words, the subset’s product must be square-free (ignoring the factor 1) and composed solely of primes that occur at most once in the factorization. Since subsets containing the number 1 do not affect the product, they have an effect in the total count by “multiplying” the number of valid combinations. The answer must be returned modulo 10^9 + 7.

Key Insights

  • Only numbers that are square-free (i.e. none of their prime factors appears more than once) can contribute to a valid product; hence, numbers like 4, 8, 9, etc. are not allowed.
  • Represent each valid number’s prime factors using a bitmask, where each bit corresponds to one of the prime numbers up to 30 (specifically: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29).
  • Use dynamic programming (DP) where the state is defined by a bitmask representing the primes that have already been used.
  • The number 1 is special: since it does not change the product, count how many times 1 appears and later multiply the result by 2^(count of 1's) (adjusting for the empty set).
  • Iterate through each valid number, updating the DP states if its corresponding bitmask does not conflict with the current state.

Space and Time Complexity

Time Complexity: O(n + (2^P * M))

  • n = length of the array (up to 10^5)
  • P = number of primes (fixed at 10)
  • M = number of valid numbers (at most 19)
    Space Complexity: O(2^P) (for the DP array)

Solution

The solution uses a DP approach leveraging bitmasking:

  1. Precompute the frequency of each number in the array.
  2. Filter out numbers that are not square‐free (except 1) and convert each valid number (2 ≤ num ≤ 30) into a bitmask based on its prime factors. If a number has a squared prime factor, skip it.
  3. Use a DP array of size 2^(number of primes) (1024) where dp[state] represents the number of ways to achieve that prime combination.
  4. For each valid number (with its frequency and bitmask), iterate over the DP states in reverse to avoid overcounting. For every state that can accommodate the new number (no overlapping prime factors), update the DP for the combined state by adding dp[old_state] * (frequency of the number).
  5. Sum up all DP states except the empty state to get the number of valid subsets.
  6. Multiply the result by 2^(frequency of 1) to account for the inclusion of ones in every subset.
  7. Return the answer modulo 10^9 + 7.

Code Solutions

MOD = 10**9 + 7

def numberOfGoodSubsets(nums):
    # Prime numbers to consider
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    
    # Frequency count for numbers [1-30]
    freq = [0] * 31
    for num in nums:
        freq[num] += 1

    # Mapping from number to its prime mask if the number is square-free.
    num_to_mask = {}
    for num in range(2, 31):
        curr_mask = 0
        valid = True
        for i, prime in enumerate(primes):
            if num % prime == 0:
                count = 0
                temp = num
                while temp % prime == 0:
                    count += 1
                    temp //= prime
                if count > 1:
                    valid = False
                    break
                curr_mask |= (1 << i)
        if valid:
            num_to_mask[num] = curr_mask

    # dp[mask] = ways to form this mask combination from valid numbers.
    dp = [0] * (1 << len(primes))
    dp[0] = 1  # base: empty subset

    # Process each number (2...30) that is square-free
    for num in range(2, 31):
        if freq[num] == 0 or num not in num_to_mask:
            continue
        mask = num_to_mask[num]
        # Update dp in reverse order over bitmask to avoid reuse in same iteration.
        for state in range((1 << len(primes)) - 1, -1, -1):
            # Only update if no conflict in prime factors.
            if (state & mask) == 0:
                dp[state | mask] = (dp[state | mask] + dp[state] * freq[num]) % MOD

    # Sum up all ways excluding the empty subset (state = 0)
    total = sum(dp[1:]) % MOD

    # Account for the ones: each 1 can be picked or not.
    # Multiply the final result by 2^(freq[1])
    total = (total * pow(2, freq[1], MOD)) % MOD
    return total

# Example usage:
print(numberOfGoodSubsets([1,2,3,4]))  # Output: 6
← Back to All Questions