1994. The Number of Good Subsets


Problem Description

You have an array of integers called nums. The task is to find the number of different subsets of nums that are considered "good." A "good" subset is one where the product of its elements can be written as the product of one or more distinct prime numbers. Specifically:

  • If a subset's product includes a repeated prime factor (like 2 * 2), it's not a "good" subset.
  • 1 has no prime factors and can be included in a "good" subset; it doesn't affect the product's prime factorization.
  • Different subsets are defined as those made by deleting different elements from nums.

The answer must be provided modulo (10^9 + 7), which is a common way to keep the numbers from getting too large by using the remainder after division by a large prime number.

For example, in an array [1, 2, 3, 4], the subset [2, 3] is good because 2 * 3 = 6 (product of distinct primes), but [4] is not good, since 4 = 2 * 2 (repeated prime).

Intuition

The intuition behind the solution is rooted in combinatorics and bitwise operations. Firstly, notice that the maximum value in nums is specified as 30, which simplifies our problem since there are only a few primes within this range.

Here's how we can think about the problem:

  1. Count the frequencies of each number in nums using a Counter.
  2. Precalculate a list of primes that we will use to check against the elements in nums.
  3. Use a bitmask to represent the inclusion of a certain prime factor in a subset product. For example, if the bitmask is 0101, it could represent that the product has prime factors of the 1st and 3rd prime numbers in our primes list.
  4. Initialize an array f where f[i] (where i is a bitmask) will represent the number of ways to get a product that has the prime factors represented by the bitmask i.
  5. Handle the special case for 1 separately, since it doesn't affect the product but it can be included or not, essentially doubling the number of subsets for each possible product.
  6. Iterate through all numbers from 2 to 30 and for each, calculate their bitmask of prime factors if they have no repeated prime factors (like 4, 9, 25, etc., which are skipped).
  7. Use dynamic programming to update the array f when considering the inclusion of each number with no repeated prime factors as you iterate through all possible states (bitmasks).
  8. The final answer is the sum of all values of f except f[0], which is the empty subset, modulo 10^9 + 7.

The solution leverages bite masks to encode the presence of prime factors elegantly and uses dynamic programming to build up the counts of valid subsets, taking into account the combination of present factors without duplication.

Learn more about Math, Dynamic Programming and Bitmask patterns.

Solution Approach

The solution approach involves the following steps:

  1. Count frequencies: Create a count of all the numbers nums using the Counter class from Python's collections. This step is necessary to handle duplicated numbers in nums.

    1cnt = Counter(nums)
  2. Modulo arithmetic: Define the modulo mod = 10**9 + 7 because we want the results modulo 10^9 + 7.

    1mod = 10**9 + 7
  3. Bitmasking for prime factors:

    • Define primes as an array of prime numbers that are less than 30 since the question limits the numbers in nums up to 30.
    • Create an array f with size 1 << len(primes) (which is 2^n where n is the number of primes). f uses bitmasks to represent subsets of primes included in the product. For example, f[0b1010] would represent the number of subsets whose product is made up of the 2nd and 4th prime numbers in the primes list.
    1primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
    2f = [0] * (1 << len(primes))
  4. Handling the special case for number 1:

    • The product of any "good" subset doesn't change if we include or exclude 1. Thus, any subset that includes 1 can appear in 2^count[1] different ways. We initialize f[0] (which includes no prime factors) to this value.
    1f[0] = pow(2, cnt[1], mod)
  5. Dynamic Programming:

    • Iterate through numbers x from 2 to 30. If a number has a square of a prime as a factor (like 4, 9, 25), we skip it since it is not a "good" subset.
    • Calculate the bitmask for the prime factors of x. If x is divisible by a prime at index i, we set the ith bit of mask to 1.
    • We then iterate through all possible states (from (1 << n) - 1 to 1) to update our f using dynamic programming. If a state contains all bits in the mask (checked with state & mask == mask), we can include x in this state. We then update f[state] by adding the ways to form the current product from the state without x times the count of x.
    • Finally, the f[state ^ mask] refers to the current state minus the prime factors of x.
    1for x in range(2, 31):
    2    if cnt[x] != 0 and x % 4 != 0 and x % 9 != 0 and x % 25 != 0:
    3        mask = 0
    4        for i, p in enumerate(primes):
    5            if x % p == 0: mask |= 1 << i
    6        for state in range((1 << n) - 1, 0, -1):
    7            if state & mask == mask:
    8                f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod
  6. Deriving the answer:

    • Iterate over all f but skip the 0 state because it includes no primes. Sum the f[i] values to get the total number of "good" subsets, and take the result modulo mod.
    1answer = sum(f[i] for i in range(1, 1 << n)) % mod
  7. The answer is returned as the final number of "good" subsets modulo 10^9 + 7.

By combining these steps—specifically the use of bitmasking, dynamic programming, and special handling for 1—the algorithm efficiently calculates the number of "good" subsets within the given constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?

Example Walkthrough

Let's illustrate the solution approach using a small example: consider the array nums = [1, 2, 3, 4, 6].

  1. Count frequencies: Using a Counter, we find that the frequencies are:

    1{1: 1, 2: 1, 3: 1, 4: 1, 6: 1}
  2. Modulo arithmetic: The results are to be presented modulo mod = 10**9 + 7.

  3. Bitmasking for prime factors:

    • Our primes array with primes less than 30 is [2, 3, 5, 7, 11, 13, 17, 19, 23, 29].
    • We create an array f of size 1 << len(primes) (1024 in this case).
  4. Handling the special case for number 1:

    • Since 1 doesn't affect the product's prime factorization, there are 2^count[1] = 2 ways to include it in any subset. We set f[0] = 2.
  5. Dynamic Programming:

    • First we consider 2: it's a prime, so its bitmask is 0b0000000001. There are 1 way to have a subset with a product of 2 (ignoring 1 for now), so f[0b0000000001] = 1.
    • Next, 3 is prime and its bitmask is 0b0000000010. There is 1 way for a subset with a product of 3, so f[0b0000000010] = 1.
    • 4 is not considered because it's not a product of distinct primes, being 2 * 2.
    • For 6 (which is 2 * 3), its mask is 0b0000000011. However, there is no state to update yet that includes both 2 and 3, so f[0b0000000011] remains 0 for now.
    • At the end of the first iteration, f looks like this (showing non-zero values only):
      1f[0b0000000000] = 2  (from the special case of '1')
      2f[0b0000000001] = 1  (from '2')
      3f[0b0000000010] = 1  (from '3')
  6. Deriving the answer:

    • Summing the non-zero f[i] values, we get 2 + 1 + 1 = 4, which we need to present modulo 10^9 + 7.
  7. Final Answer: After iterating through the other numbers in nums and updating the f array accordingly, the final answer would be the sum of all valid f[i] values after completing the dynamic programming (modulo mod). In our small example case, we would need to continue the dynamic programming steps for 6, which would increase the count of f[0b0000000011], and then take the sum of the f array (excluding f[0]) modulo mod.

In a fully worked-through solution with the remaining numbers, we would use the above process to dynamically update the f array with all combinations of primes represented by the numbers in nums. This method ensures, through the use of bitmasks and the dynamic array f, that only "good" subsets (those with unique prime factors) are considered in the final count, adhering to the rules of the problem.

Solution Implementation

1from collections import Counter
2
3class Solution:
4    def numberOfGoodSubsets(self, nums: List[int]) -> int:
5        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]  # List of primes up to 29
6        count = Counter(nums)  # Count frequency of each number in 'nums'
7        mod = 10**9 + 7  # Define the modulus for taking the result modulo 1e9+7
8        num_primes = len(primes)
9        dp = [0] * (1 << num_primes)  # dp[state] will keep track of the count of good subsets for a given state
10        dp[0] = pow(2, count[1], mod)  # Initiate the dp[0] state with the count of subsets containing '1's
11      
12        # Iterate through numbers 2 to 30 to update dp with good subsets counts
13        for x in range(2, 31):
14            if count[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0:
15                continue  # Skip if the number is not present or is a square
16          
17            bit_mask = 0  # Will hold unique prime factors of 'x' as bit positions
18            for i, prime in enumerate(primes):
19                if x % prime == 0:
20                    bit_mask |= 1 << i  # Set the bit corresponding to the prime number
21          
22            # Traverse all combinations of prime factors (states) and update counts
23            for state in range((1 << num_primes) - 1, 0, -1):
24                if state & bit_mask == bit_mask:  # Check if 'state' includes all prime factors of 'x'
25                    dp[state] = (dp[state] + count[x] * dp[state ^ bit_mask]) % mod
26      
27        # Sum up all counts except the empty subset (which is dp[0])
28        result = sum(dp[i] for i in range(1, 1 << num_primes)) % mod
29        return result
30
1class Solution {
2    public int numberOfGoodSubsets(int[] nums) {
3        // Initialize prime numbers up to 30 (inclusive)
4        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
5
6        // Count the frequency of each number in the given array
7        int[] count = new int[31];
8        for (int num : nums) {
9            ++count[num];
10        }
11
12        // Define the modulo for performing operations under, to avoid overflow issues
13        final int MOD = (int) 1e9 + 7;
14
15        // Initialize the number of primes
16        int numPrimes = primes.length;
17
18        // Create a dynamic programming array to store ways of forming a good subset ending with the prime bitmask
19        long[] dp = new long[1 << numPrimes];
20        dp[0] = 1;
21
22        // Account for the number 1 which can be included in any subset, contributing to the count by multiplying by 2
23        for (int i = 0; i < count[1]; ++i) {
24            dp[0] = (dp[0] * 2) % MOD;
25        }
26
27        // Go through the numbers 2 to 30 and update the dp array for each possible subset
28        for (int x = 2; x < 31; ++x) {
29            // Skip numbers with zero count or that are squares of other primes
30            if (count[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
31                continue;
32            }
33
34            // Calculate the bitmask for the current number based on its prime factors
35            int mask = 0;
36            for (int i = 0; i < numPrimes; ++i) {
37                if (x % primes[i] == 0) {
38                    mask |= 1 << i;
39                }
40            }
41
42            // Update the dp array from the end to the beginning to avoid revisiting updated states
43            for (int state = (1 << numPrimes) - 1; state > 0; --state) {
44                // Only update the dp array if the current state contains the prime factors of x
45                if ((state & mask) == mask) {
46                    dp[state] = (dp[state] + count[x] * dp[state ^ mask]) % MOD;
47                }
48            }
49        }
50
51        // Sum up all the dp values except for the empty subset to get the final answer
52        long answer = 0;
53        for (int i = 1; i < 1 << numPrimes; ++i) {
54            answer = (answer + dp[i]) % MOD;
55        }
56
57        // Return the final answer as an integer
58        return (int) answer;
59    }
60}
61
1class Solution {
2public:
3    int numberOfGoodSubsets(vector<int>& nums) {
4        // Array of the first 10 prime numbers
5        int primes[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
6
7        // Count array initialized to zero for numbers 1 to 30
8        int count[31] = {};
9        // Count the frequency of each number in the nums array
10        for (int x : nums) {
11            ++count[x];
12        }
13
14        // Number of prime numbers considered
15        int numPrimes = 10;
16
17        // Modulus for handling large numbers
18        const int mod = 1e9 + 7;
19
20        // Dynamic programming (DP) table to store the number of good subsets per state
21        vector<long long> dp(1 << numPrimes);
22        dp[0] = 1;
23
24        // Account for the number of times 1 appears, since it can be part of any subset
25        for (int i = 0; i < count[1]; ++i) {
26            dp[0] = dp[0] * 2 % mod;
27        }
28
29        // Iterate through 2 to 30 to update the DP table accordingly
30        for (int x = 2; x < 31; ++x) {
31            // Skip processing if the count is 0 or if the number has duplicate prime factors
32            if (count[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
33                continue;
34            }
35
36            // Binary representation of the number's prime factors
37            int mask = 0;
38            for (int i = 0; i < numPrimes; ++i) {
39                if (x % primes[i] == 0) {
40                    mask |= 1 << i;
41                }
42            }
43
44            // Update the DP table states for the current number with its count
45            for (int state = (1 << numPrimes) - 1; state > 0; --state) {
46                if ((state & mask) == mask) {
47                    dp[state] = (dp[state] + static_cast<long long>(count[x]) * dp[state ^ mask]) % mod;
48                }
49            }
50        }
51
52        // Calculate the final answer by summing up all good subsets excluding the empty set
53        long long answer = 0;
54        for (int i = 1; i < (1 << numPrimes); ++i) {
55            answer = (answer + dp[i]) % mod;
56        }
57
58        // Return the computed number of good subsets as an integer
59        return static_cast<int>(answer);
60    }
61};
62
1// Constants for prime numbers and modulus
2const primes: number[] = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
3const mod: number = 1e9 + 7;
4
5// Define the count array and initialize it to zeroes
6let count: number[] = new Array(31).fill(0);
7
8// Function to count the frequency of each number in the nums array
9function countFrequencies(nums: number[]): void {
10    for (let x of nums) {
11        ++count[x];
12    }
13}
14
15// Function to compute the number of good subsets
16function numberOfGoodSubsets(nums: number[]): number {
17    countFrequencies(nums);
18
19    const numPrimes: number = primes.length;
20
21    // DP table to store the number of good subsets for each state
22    let dp: bigint[] = new Array(1 << numPrimes).fill(BigInt(0));
23    dp[0] = BigInt(1);
24
25    // Account for the presence of 1, as it can be part of any subset
26    for (let i = 0; i < count[1]; ++i) {
27        dp[0] = dp[0] * BigInt(2) % BigInt(mod);
28    }
29
30    // Iterate through numbers 2 to 30, updating the DP table for each
31    for (let x = 2; x <= 30; ++x) {
32        // Skip if count is zero or if the number has repeated prime factors
33        if (count[x] === 0 || x % 4 === 0 || x % 9 === 0 || x % 25 === 0) continue;
34
35        // Create bitmask representation of the number's prime factors
36        let mask: number = 0;
37        for (let i = 0; i < numPrimes; ++i) {
38            if (x % primes[i] === 0) {
39                mask |= 1 << i;
40            }
41        }
42
43        // Update DP table states for the current number, considering its count
44        for (let state = (1 << numPrimes) - 1; state > 0; --state) {
45            if ((state & mask) === mask) {
46                dp[state] = (dp[state] + BigInt(count[x]) * dp[state ^ mask]) % BigInt(mod);
47            }
48        }
49    }
50
51    // Sum up all good subsets, excluding the empty set
52    let answer: bigint = BigInt(0);
53    for (let i = 1; i < (1 << numPrimes); ++i) {
54        answer = (answer + dp[i]) % BigInt(mod);
55    }
56
57    // Return the computed number of good subsets
58    return Number(answer);
59}
60
61// Example usage
62// const nums: number[] = [1, 2, 3, ...]; // Fill with your set of numbers
63// const result: number = numberOfGoodSubsets(nums);
64

Time and Space Complexity

Time Complexity

The time complexity of the given code is determined by several nested loops and operations on the Counter object.

  1. Counting the frequency of each number takes O(n), where n is the length of the nums list.
  2. Calculating pow(2, cnt[1], mod) is O(log(cnt[1])), which is the complexity of the exponentiation operation.
  3. The loop from 2 to 30 for each number x is run 29 times (O(1) since it's a constant), and within this loop:
    • Checking whether x is divisible by 4, 9, or 25 is O(1).
    • Constructing the mask requires iterating over the list of primes, which is O(m) where m is the number of primes (len(primes)).
  4. The most significant loop is the nested loop that iterates over all states of the f array. There are (1 << n) states, which is 2^n, iterated for each x. The bitwise operations inside the loop are O(1) operations. Therefore, the nested loop's complexity is O(2^n * m).

Overall, the most time-consuming part is the nested loop with a complexity of O(2^n * m), where n is the number of primes considered (n = 10 here) and m is the count of numbers between 2 and 30 for which frequency is calculated. Consequently, the overall time complexity is O(2^n * m) which simplifies to O(2^10 * 29).

Space Complexity

The space complexity of the code is determined by the additional data structures that are used:

  1. The cnt Counter object has at most 30 key-value pairs corresponding to the numbers from 1 to 30, thus O(1) space.
  2. The f array has (1 << n) elements, which is 2^n, yielding O(2^n) space complexity.

The dominant factor is the space required for the f array. Hence, the overall space complexity is O(2^n), where n is the number of primes.

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


Fast Track Your Learning with Our Quick Skills Quiz:

How many ways can you arrange the three letters A, B and C?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄