2572. Count the Number of Square-Free Subsets

Problem Description

You are given a positive integer array nums that is 0-indexed. The task is to calculate the number of non-empty subsets of this array such that the product of the elements in any of these subsets is a square-free integer. A square-free integer is one that is not divisible by any perfect square other than 1. For instance, 6 is square-free since its divisors 1, 2, 3, and 6 are not perfect squares (other than 1), but 12 is not square-free because it's divisible by 4, which is a perfect square.

The subset must be considered square-free as an entirety, meaning that the product of all its elements mustn't have a square factor larger than 1. Note that subsets must be non-empty and can be created by removing any number of elements, except all, from the nums array. Different combinations of indices to delete lead to different subsets.

Due to the potentially large number of square-free subsets, the result should be returned modulo 10^9 + 7.

To summarize:

• A non-empty subset is square-free if its product is a square-free integer.
• Calculate the number of such subsets.
• The result is a large number, hence return modulo 10^9 + 7.

Intuition

The core of the solution leverages bitwise operations to effectively manage the complexity of finding square-free subsets. The idea hinges on the fact that each prime factor can only appear once in the square-free subset's product, otherwise it would not be square-free. We use bitmasks to represent the subset of prime factors that are contained in each element's prime factorisation.

The first part of the solution involves setting up prime numbers and a bitmask for each number x in the nums array. We only consider the primes up to 29 because the problem specifies that nums only contains positive integers up to 30, which means none of them will have a prime factor greater than 29. We also discount any numbers that are square numbers themselves (e.g., 4, 9, 25) as they cannot be part of a square-free product.

We create a bitmask for each prime, where each bit position corresponds to a particular prime. If a number includes a prime in its factorization, the corresponding bit is set to 1.

Then for each number and its count in nums, we update our subset counts (f) using their bitmasks. The subset counts (f) keep track of all possible combinations of prime factors up to this point; they represent how many ways we can get a certain combination of prime factors from the subsets analyzed so far.

Each element in nums is accounted for by evaluating the bitwise 'AND' (&) of its bitmask with each state (combination of prime factors represented as a bitmask) in f. If the result is the same as the bitmask, it means the current subset's product can be formed by multiplying the products represented by the state and the new element.

After processing all elements in nums, the sum of all counts in f gives the total number of square-free subsets. We subtract 1 because the empty subset is included in our calculations, but the problem asks for non-empty subsets only.

Learn more about Math, Dynamic Programming and Bitmask patterns.

Solution Approach

The solution approach involves a few key algorithmic strategies and data structures:

• Bitmasking: The main tool used here is bitmasking, which is a way to represent subsets of primes. Each bit in an integer represents whether a specific prime number is in the product of the subset. With this, it's easy to manipulate and combine prime factors using bitwise operations.

• Dynamic Programming (DP): The problem is approached using a bottom-up dynamic programming technique. An array f is maintained, where f[state] represents the number of ways to form a square-free product whose prime factors are indicated by the state. Here, state is an integer where each bit corresponds to whether a prime factor (from a pre-defined list of primes) is present in the subset.

• Modular Arithmetic: To handle potentially large numbers, modular arithmetic is implemented (with the modulus given as 10^9 + 7) to ensure that all intermediate and final calculations fit within standard integer range.

• Prime Factorization: As part of the pre-processing, only numbers up to 30 are considered, and so, a fixed list of primes that are less than 30 is used. Then, a mask is created for each number based on its prime factors.

• Enumeration of Subsets: The actual enumeration of subsets is done by iterating over all possible states of prime combinations, represented by f. If a number has prime factors corresponding to a given state, it could be included in subsets that don’t have these primes already – hence the states are updated to reflect the new combinations.

Let's break down the key parts of the reference solution:

• Initialize the primes list for reference and a counter for occurrences of each element in nums.
• Set up a DP array f with 1 << n elements, initialized to 0. Here, n is the number of primes considered, and 1 << n represents 2 to the power of n, which is the number of possible combinations of the primes. The first element f[0] is initially set to 2^cnt[1] to handle the special case of 1s in nums.
• Iterate over each possible element x (from 2 to 30, since 1 is already handled) and continue only if x is not a square number (x % 4, x % 9, and x % 25) and has a non-zero count in the array.
• For each such element x, calculate its bitmask (mask), which determines which primes (out of the first 10) divide it.
• Then update the DP array f. For every state (existing combination of prime factors), check whether adding the new element x represented by mask would still keep the product square-free. This is done by using the bitwise AND operation. If the condition is true, update f[state] by adding the count of x times the count of combinations without the new primes.
• Finally, the sum of all elements in f minus 1 (for the empty subset) is the total number of non-empty, square-free subsets. This value is returned modulo 10^9 + 7.

By using this approach, the problem of counting subsets is reduced from a potentially exponential brute force check to a manageable DP solution that runs in polynomial time relative to the size of the input and the number of considered primes.

Example Walkthrough

Let's illustrate the solution approach with an example. Consider the array nums = [1, 2, 3, 4, 5]. We wish to find the number of non-empty, square-free subsets.

First, we initialize our primes list for reference, which in the context of nums is [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] because we're only considering numbers up to 30. We also initialize an array f with a size of 1 << 10 (1024) because we have 10 primes and thus 2^10 possible combinations.

We handle the number 1 as a special case, setting f[0] = 2 because there is one number 1 in nums, and it can be present or absent to form a subset (hence the power of 2). The 0 state here represents an empty prime factor set, which corresponds to any subset solely containing any number of 1's.

For each number x in nums that isn't a square number (4 from our example is excluded):

1. We calculate a bitmask representing the prime factors of x. For example, the number 2 has a bitmask of 0000000001, 3 has 0000000010, and 5 has 0000000100, etc.

2. We iterate through the DP array f, checking each state. To consider adding the number x to a subset represented by state, we perform (state & mask) == 0. If this is true, x can be added without making the subset's product divisible by a perfect square. We then update f[new state] where new state = state | mask, meaning we add the prime factors of x to the state. This operation is carried out under modulo 10^9 + 7.

For the number 2, which has a bitmask of 0000000001:

• f[0] represents subsets without any of the prime numbers considered, so we update f[0000000001] to be f[0000000001] + f[0].

For the number 3, which has a bitmask of 0000000010:

• f[0] and f[0000000001] are valid states that could add 3 without creating a square number, so we update f[0000000010] and f[0000000011] accordingly.

For the number 5, with the bitmask 0000000100:

• Again, we look for states where adding 5 does not introduce a square. This leads to updates of states like f[0000000100], f[0000000101], and f[0000000110].

Following this approach for all permissible x in nums, we sum all the valid subsets from the DP array f. The total count of square-free subsets would then be the sum of f minus 1 (the initial state) to exclude the empty set.

Finally, we take the result modulo 10^9 + 7. If we follow through with the process for all eligible numbers in the provided array nums, we shall arrive at the required count of square-free subsets.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is primarily determined by the number of iterations in the nested loops.

The outer for-loop iterates over a range of numbers from 2 to 30, which is fixed and doesn't scale with input size. Therefore, its contribution to time complexity is constant, O(1).

However, the critical part is the nested loop iterating over the possible states represented by the binary mask. Since there are n primes being considered, and each prime corresponds to a bit in the mask, there are 2^n possible states. The loop iterates through all those states for each x considered in the outer loop, which results in a total of O(2^n) iterations for the inner loop.

Given that n corresponds to the length of the primes list, which contains 10 primes, n = 10. Thus, the dominating term for the time complexity is O(2^10), which simplifies to O(1024).

Because the outer for-loop's complexity is constant, and the inner loop runs in O(1024), the overall time complexity remains O(1024), which can be considered constant-time, O(1), because it does not vary with the input size.

Space Complexity

The space complexity can be analyzed by looking at the space allocated for data structures independent of the input size.

Here, the primary data structures are:

• The primes list, which contains a constant number of elements, contributing O(1) space.
• The cnt counter, which may contain up to 30 key-value pairs—one for each number from 2 to 30—yielding O(1) space.
• The f list, which holds 2^n elements where n is the number of prime numbers considered (10 in this case). Thus, the space complexity for the list f is O(1024).

As 1024 is a constant number, the space required for f does not change with input size, and its contribution to space complexity is O(1).

Adding these together, the overall space complexity of the algorithm is O(1) since all components contribute constant space.

In summary, the time complexity is O(1) and the space complexity is O(1). It should be noted that while mathematically expressed as O(1), in practice, this might be considered inefficient due to the large constant factors involved.

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