Introduction

In this blog post, we will explore how to solve the LeetCode problem "1994" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

You are given an integer array nums. We call a subset of nums good if its product can be represented as a product of one or more distinct prime numbers. For example, if nums = [1, 2, 3, 4]: [2, 3], [1, 2, 3], and [1, 3] are good subsets with products 6 = 23, 6 = 23, and 3 = 3 respectively. [1, 4] and [4] are not good subsets with products 4 = 22 and 4 = 22 respectively. Return the number of different good subsets in nums modulo 109 + 7. A subset of nums is any array that can be obtained by deleting some (possibly none or all) elements from nums. Two subsets are different if and only if the chosen indices to delete are different. Example 1: Input: nums = [1,2,3,4] Output: 6 Explanation: The good subsets are: - [1,2]: product is 2, which is the product of distinct prime 2. - [1,2,3]: product is 6, which is the product of distinct primes 2 and 3. - [1,3]: product is 3, which is the product of distinct prime 3. - [2]: product is 2, which is the product of distinct prime 2. - [2,3]: product is 6, which is the product of distinct primes 2 and 3. - [3]: product is 3, which is the product of distinct prime 3. Example 2: Input: nums = [4,2,3,15] Output: 5 Explanation: The good subsets are: - [2]: product is 2, which is the product of distinct prime 2. - [2,3]: product is 6, which is the product of distinct primes 2 and 3. - [2,15]: product is 30, which is the product of distinct primes 2, 3, and 5. - [3]: product is 3, which is the product of distinct prime 3. - [15]: product is 15, which is the product of distinct primes 3 and 5. Constraints: 1 <= nums.length <= 105 1 <= nums[i] <= 30

Explanation

Here's the solution:

• Prime Masking: Represent each number from 1 to 30 by a bitmask indicating the presence of its prime factors (2, 3, 5, 7, 11, 13, 17, 19, 23, 29).
• Dynamic Programming: Use dynamic programming to count the number of good subsets. The state represents the bitmask of distinct primes used so far. For each number, we either include it in a subset if it doesn't introduce duplicate primes or exclude it.

• Handling Ones: Account for the number of '1's in the input array separately since they don't affect whether a subset is good or not.

• Time & Space Complexity: O(N + 2¹⁰), where N is the length of the input array. Space Complexity is O(2¹⁰).

Code

    def square_free_subsets(nums):
    MOD = 10**9 + 7
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    prime_mask = [0] * 31
    good = [False] * 31

    for i in range(2, 31):
        is_good = True
        mask = 0
        num = i
        for j, p in enumerate(primes):
            if num % (p * p) == 0:
                is_good = False
                break
            if num % p == 0:
                mask |= (1 << j)
                num //= p
        if is_good:
            prime_mask[i] = mask
            good[i] = True

    dp = [0] * (1 << 10)
    dp[0] = 1
    count_one = 0

    for num in nums:
        if num == 1:
            count_one += 1
            continue

        if good[num]:
            mask = prime_mask[num]
            for i in range(1 << 10):
                if (i & mask) == 0:
                    dp[i | mask] = (dp[i | mask] + dp[i]) % MOD

    ans = 0
    for i in range(1 << 10):
        ans = (ans + dp[i]) % MOD

    ans = (ans - 1 + MOD) % MOD  # Exclude the empty set
    ans = (ans * pow(2, count_one, MOD)) % MOD

    return ans