Count the Number of Square-Free Subsets

Medium

Asked by:

17 views

Topics:

Dynamic ProgrammingBit Manipulation

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⁹ + 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 0^th element [3]. The product of its elements is 3, which is a square-free integer.
- The subset consisting of the 3^rd element [5]. The product of its elements is 5, which is a square-free integer.
- The subset consisting of 0^th and 3^rd 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 0^th 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

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers in the input array? Can a number be zero, negative, or exceed a certain limit?
What is the maximum size of the input array? I'm considering how this might affect memory and algorithm choices.
Are there any duplicate numbers in the input array, and if so, how should they be handled when forming subsets?
If no square-free subset exists, what value should I return?
Can you provide a more formal definition of 'square-free' in the context of this problem? Specifically, what constitutes a 'square' factor we need to avoid?

Brute Force Solution

Approach

The brute-force strategy for this problem involves examining every possible combination of numbers from the given set. We check each combination to see if it meets the criteria of being 'square-free.' The goal is to count all the valid combinations.

Here's how the algorithm would work step-by-step:

Consider each number in the given set individually.
Then, look at all possible pairs of numbers.
Next, examine all possible groups of three numbers, then four, and so on, up to the entire set of numbers.
For each combination of numbers we select, determine if the product of the numbers is square-free. This means checking if that product has any repeated prime factors (like 4, 9, or 25).
If the product is square-free, we increase our count.
After checking every possible combination, the final count will tell us the number of square-free subsets.

Code Implementation

def count_square_free_subsets_brute_force(numbers):
    list_length = len(numbers)
    square_free_subset_count = 0

    # Iterate through all possible subsets using bit manipulation
    for i in range(1, 2**list_length):
        subset_product = 1
        
        current_subset = []
        for j in range(list_length):
            # Check if j-th element is present in the subset
            if (i >> j) & 1:
                current_subset.append(numbers[j])
                subset_product *= numbers[j]

        # Check if the product is square-free
        if is_square_free(subset_product):
            # Increment the count of square-free subsets
            square_free_subset_count += 1

    return square_free_subset_count

def is_square_free(number):
    if number <= 1:
        return True

    # Iterate from 2 to the square root of the number
    for i in range(2, int(number**0.5) + 1):
        # Check if i*i is a factor. If so, it's not square-free.
        if number % (i*i) == 0:
            return False

    return True

Big(O) Analysis

Time Complexity

O(2^n) – The algorithm iterates through all possible subsets of the input set. For a set of size 'n', there are 2^n possible subsets. For each subset, we compute the product of its elements and check if the product is square-free, which takes O(k) time where k is the size of the subset. Since we are doing this for every one of the 2^n subsets, and the cost to compute and check square-freeness is directly proportional to the subset size (which in worst case, is 'n'), the dominating factor is still the generation of all possible subsets, making the overall time complexity O(2^n).

Space Complexity

O(1) – The provided brute-force approach, when implemented, primarily uses variables to track the current subset being considered and a counter for square-free subsets. The number of these variables remains constant regardless of the input set size N. No auxiliary data structures like lists, arrays, or hashmaps are explicitly created to store intermediate results during the subset generation or square-free check. Therefore, the auxiliary space required does not scale with the input size, making it constant.

Optimal Solution

Approach

The core idea is to avoid redundant calculations by focusing only on square-free numbers and using dynamic programming. We'll identify square-free numbers and then build up subsets incrementally, keeping track of the number of ways to form each possible square-free product. This significantly cuts down the search space.

Here's how the algorithm would work step-by-step:

First, identify which numbers in the input are square-free. A square-free number is not divisible by any perfect square greater than 1 (like 4, 9, 16, etc.).
Recognize that the number '1' is special because any subset can either include or exclude it, doubling the total number of subsets for a given set of square-free products.
Create a way to remember the number of subsets which yield a particular product of square-free numbers. This can be done with a table or dictionary.
Go through each square-free number in the input one at a time.
For each square-free number, consider how it interacts with the products we already know how to make. For each existing product, multiply it by the current square-free number to get a new product.
Update our table to add the number of ways to get the new product. This number is the sum of existing ways to make the initial product (before multiplying by the new number).
After going through all the square-free numbers, sum up the number of ways to form each product recorded in our table.
Finally, remember the special case of the number '1'. If '1' was in the original input, double the answer to account for the subsets that include '1' and those that don't.

Code Implementation

def count_square_free_subsets(numbers):
    MODULO = 10**9 + 7

    def is_square_free(number):
        for factor in range(2, int(number**0.5) + 1):
            if number % (factor * factor) == 0:
                return False
        return True

    square_free_numbers = [number for number in numbers if is_square_free(number)]

    has_one = square_free_numbers.count(1)
    square_free_numbers = [number for number in square_free_numbers if number != 1]

    product_counts = {1: 1}

    # Iterate through each square-free number to build subsets
    for square_free_number in square_free_numbers:
        new_product_counts = product_counts.copy()

        for existing_product, existing_count in product_counts.items():
            new_product = existing_product * square_free_number

            # Update counts only for valid square-free products
            if is_square_free(new_product):
                new_product_counts[new_product] = (new_product_counts.get(new_product, 0) + existing_count) % MODULO

        product_counts.update(new_product_counts)

    total_count = 0

    # Sum up the ways to achieve each square-free product.
    for count in product_counts.values():
        total_count = (total_count + count) % MODULO

    # Handle the '1' case: double the subsets for each '1' found.
    for _ in range(has_one):
        total_count = (total_count * 2) % MODULO

    return total_count

Big(O) Analysis

Time Complexity

O(n * targetRange) – Let n be the size of the input array nums, and targetRange be the maximum possible square-free product which is bounded by the product of distinct prime numbers less than or equal to the largest number in nums (capped at 30). The algorithm iterates through each of the n numbers in the input array. For each square-free number, it iterates through all possible products currently stored in the dynamic programming table. The size of the DP table is at most the targetRange since each entry represents a unique square-free product. Thus, in the worst case, the time complexity is O(n * targetRange) because for each of the n square-free numbers, we iterate through up to targetRange existing products.

Space Complexity

O(M) – The primary auxiliary space usage comes from the table (or dictionary) used to store the number of subsets that yield a particular product of square-free numbers, where M is the maximum possible product of square-free numbers. The size of this table depends on the range of numbers in the input and grows as the potential products increase, independent of the input size N (number of elements in the input array). Therefore, the space complexity is determined by the range of possible products, and can be represented as O(M), where M is the maximum product.

Edge Cases

Case	How to Handle
Empty input array	Return 1, as there is one square-free subset, the empty set.
Array containing the number 1	The number 1 can be included in any square-free subset, so it requires special handling to account for its multiplicative effect on the number of possible subsets.
Array with a single element that is a perfect square	This element cannot be part of any valid subset, so it is ignored.
Array with all elements being perfect squares	The result is 1 because the only valid square-free subset is the empty set.
Large input array size, leading to potential memory issues with DP table	The dynamic programming table size is based on the product of prime numbers which is fixed, but modular arithmetic is required to prevent integer overflow.
Input array contains duplicate non-square numbers	The number of valid subsets will increase and we must take duplicates into account when calculating possible combinations.
Numbers in the input array exceed the largest precomputed squarefree number	Any number larger than the upper limit should be either reduced to its largest square-free factor under the limit or treated as invalid.
Integer overflow during the calculation of the result using modulo arithmetic	Perform modulo operations after each multiplication to prevent integer overflow and ensure the result stays within the valid range.

Empty input array

How to Handle:

Return 1, as there is one square-free subset, the empty set.

Array containing the number 1

How to Handle:

The number 1 can be included in any square-free subset, so it requires special handling to account for its multiplicative effect on the number of possible subsets.

Array with a single element that is a perfect square

How to Handle:

This element cannot be part of any valid subset, so it is ignored.

Array with all elements being perfect squares

How to Handle:

The result is 1 because the only valid square-free subset is the empty set.

Large input array size, leading to potential memory issues with DP table

How to Handle:

The dynamic programming table size is based on the product of prime numbers which is fixed, but modular arithmetic is required to prevent integer overflow.

Input array contains duplicate non-square numbers

How to Handle:

The number of valid subsets will increase and we must take duplicates into account when calculating possible combinations.

Numbers in the input array exceed the largest precomputed squarefree number

How to Handle:

Any number larger than the upper limit should be either reduced to its largest square-free factor under the limit or treated as invalid.

Integer overflow during the calculation of the result using modulo arithmetic

How to Handle:

Perform modulo operations after each multiplication to prevent integer overflow and ensure the result stays within the valid range.