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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count the Number of Square-Free Subsets

Difficulty: Medium

Problem Description

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 10^9 + 7.

Key Insights

  • A square-free integer does not have any prime factor with an exponent greater than 1.
  • The range of input values (1 <= nums[i] <= 30) allows for efficient prime factorization.
  • The problem can be approached using bit manipulation to explore subsets.
  • We need to ensure that when constructing subsets, we do not include elements that will introduce square factors.

Space and Time Complexity

Time Complexity: O(n * 2^n) in the worst case, where n is the number of elements in nums. Space Complexity: O(n) for storing prime factorizations.

Solution

To solve the problem, we will:

  1. Precompute the prime factorization of each number from 1 to 30.
  2. Use a bitmask to represent the inclusion or exclusion of each element in nums.
  3. For each subset represented by a bitmask, calculate the product of the selected elements and check if it is square-free by examining its prime factors.
  4. Count and return the number of valid square-free subsets modulo 10^9 + 7.

Code Solutions

MOD = 10**9 + 7

def is_square_free(num):
    factor_count = {}
    for i in range(2, int(num**0.5) + 1):
        while num % i == 0:
            if i in factor_count:
                factor_count[i] += 1
            else:
                factor_count[i] = 1
            num //= i
    if num > 1:
        factor_count[num] = 1
    return all(count < 2 for count in factor_count.values())

def count_square_free_subsets(nums):
    n = len(nums)
    square_free_count = 0
    for mask in range(1, 1 << n):
        product = 1
        for i in range(n):
            if mask & (1 << i):
                product *= nums[i]
        if is_square_free(product):
            square_free_count = (square_free_count + 1) % MOD
    return square_free_count

# Example usage
print(count_square_free_subsets([3, 4, 4, 5]))  # Output: 3
← Back to All Questions