Count the Number of Square-Free Subsets Interview Question for Google

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.

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.

For example:

nums = [3,4,4,5] should return 3. The valid subsets are:

[3] (product is 3)
[5] (product is 5)
[3,5] (product is 15)

nums = [1] should return 1, as the only subset is [1].

Constraints:

1 <= nums.length <= 1000
1 <= nums[i] <= 30

MOD = 10**9 + 7

def square_free_subsets(nums):
    # Precompute a mask for each number from 1 to 30, where each bit in the mask
    # represents a prime number. If a number is divisible by the square of a prime, the mask is -1.
    prime_squares = [4, 9, 25]
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    masks = [0] * 31
    for i in range(1, 31):
        mask = 0
        for j, p in enumerate(primes):
            if i % (p * p) == 0:
                mask = -1
                break
            if i % p == 0:
                mask |= (1 << j)
        masks[i] = mask

    # dp[mask] will store the number of square-free subsets that have a product with the given mask
    dp = {}
    dp[0] = 1  # Empty subset has product 1, which is square-free

    for num in nums:
        mask = masks[num]
        if mask == -1:  # Number is divisible by a square, skip it
            continue
        new_dp = dp.copy()
        for prev_mask, count in dp.items():
            if (prev_mask & mask) == 0:
                new_mask = prev_mask | mask
                new_dp[new_mask] = (new_dp.get(new_mask, 0) + count) % MOD
        dp = new_dp

    # Sum all non-empty subsets that are square-free
    total_count = 0
    for mask, count in dp.items():
        if mask != 0:
            total_count = (total_count + count) % MOD

    return total_count

# Example usage
nums1 = [3, 4, 4, 5]
print(f"Number of square-free subsets for {nums1}: {square_free_subsets(nums1)}")  # Output: 3

nums2 = [1]
print(f"Number of square-free subsets for {nums2}: {square_free_subsets(nums2)}")  # Output: 1

nums3 = [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
print(f"Number of square-free subsets for a larger array: {square_free_subsets(nums3)}")

nums4 = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
print(f"Number of square-free subsets for array of primes: {square_free_subsets(nums4)}")

Explanation:

Problem Definition:
- Given an array nums, find the number of non-empty subsets such that the product of the elements in each subset is a square-free integer.
Square-Free Integer:
- An integer not divisible by any perfect square other than 1.
Approach:
- Dynamic programming with bit masking.
Algorithm:
- Masking:
  - Create a mask for each number from 1 to 30. This mask represents the prime factors of the number.
  - The first 10 prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.
  - If a number is divisible by the square of any of these primes, its mask is set to -1 (invalid).
- Dynamic Programming:
  - dp[mask] stores the number of square-free subsets with the given mask (combination of prime factors).
  - Initialize dp[0] = 1 (empty subset has product 1, which is square-free).
  - Iterate through each number in nums:
    - If the number's mask is valid (not -1):
      - Iterate through the existing dp dictionary.
      - If the current mask and the number's mask have no common bits (meaning their product is square-free):
        
        Combine the masks by performing a bitwise OR.
        
        Update the count of the new mask in the dp dictionary.
- Result:
  - Sum the counts of all non-empty subsets in the dp dictionary modulo 10^9 + 7.

Example:

For nums = [3, 4, 4, 5]:

Masks: masks[3] = 2, masks[4] = -1, masks[5] = 4 (assuming 2, 3, 5 are mapped to indices 0, 1, 2 in the prime array).
Valid numbers: 3, 5
DP transitions:
- Initial: dp[0] = 1
- Number 3: dp[2] = 1
- Number 5: dp[4] = 1, dp[6] = 1 (2 | 4)
Square-free subsets: [3], [5], [3, 5]
Count: 3

Time Complexity: O(N * 2^P), where N is the length of nums and P is the number of primes (in this case, 10).

Space Complexity: O(2^P), where P is the number of primes.

Edge Cases:

Input with numbers greater than 30: The problem statement constrains the input numbers to be between 1 and 30 inclusive, so no handling is needed for larger numbers.
Duplicate numbers: The algorithm correctly handles duplicate numbers, as each valid number contributes to the count of subsets.
Empty Input: If the input list nums is empty, the function will return 0 since the problem asks for non-empty subsets.
Large Number of Square-Free Numbers: The algorithm will efficiently handle larger arrays with more square-free numbers, though the space complexity remains O(2^P), where P is number of primes. The time complexity is O(N * 2^P).
Numbers with Square Factors: Numbers like 4, 8, 9 are automatically excluded by the mask = -1 filtering.