How do you solve The Number of Good Subsets on LeetCode?

The Number of Good Subsets (LeetCode #1994) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n * log(max(nums))) time complexity and O(n) space complexity. Key insight: Only consider numbers with distinct prime factors, as they contribute to good subsets.

What is the brute force solution for The Number of Good Subsets?

The brute force approach for The Number of Good Subsets is Brute Force, with O(n²) time complexity and O(1) space complexity. We can generate all possible subsets of the array and check if their products are good. This is straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n * log(max(nums))).

What are the interview tips for The Number of Good Subsets?

Clearly explain your thought process when generating subsets or using bit manipulation. Be cautious with edge cases, especially with the number 1 and duplicates. Practice prime factorization and bit manipulation to become comfortable with these concepts.

What are common mistakes when solving The Number of Good Subsets?

Failing to account for the number 1, which does not contribute to good subsets. Not properly handling the bitmask representation of prime factors.

#1994

The Number of Good Subsets

Hard

ArrayHash TableMathDynamic ProgrammingBit ManipulationCountingNumber TheoryBitmaskHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n * log(max(nums)))
Space	O(1)	O(n)

💡

Intuition

Time O(n * log(max(nums)))Space O(n)

Instead of generating all subsets, we can use bit manipulation to efficiently count good subsets based on prime factorization.

⚙️

Algorithm

3 steps

1Step 1: Identify the distinct prime factors of each number in the input array.
2Step 2: Use a bitmask to represent the combination of prime factors for each number.
3Step 3: Count the frequency of each unique bitmask and calculate the number of good subsets using combinatorial counting.

solution.py29 lines

1# Full working Python code
2from collections import defaultdict
3
4def prime_factors(n):
5    factors = set()
6    for i in range(2, int(n**0.5) + 1):
7        while n % i == 0:
8            factors.add(i)
9            n //= i
10    if n > 1:
11        factors.add(n)
12    return factors
13
14def count_good_subsets(nums):
15    MOD = 10**9 + 7
16    factor_map = defaultdict(int)
17    for num in nums:
18        if num == 1:
19            continue
20        primes = prime_factors(num)
21        mask = 0
22        for prime in primes:
23            mask |= (1 << (prime - 2))  # Using primes starting from 2
24        factor_map[mask] += 1
25
26    count = 1  # For the empty subset
27    for freq in factor_map.values():
28        count = count * (pow(2, freq, MOD) - 1) % MOD
29    return count

ℹ

Complexity note: The time complexity is O(n * log(max(nums))) due to the prime factorization step for each number, which is efficient compared to the brute-force approach.

1Only consider numbers with distinct prime factors, as they contribute to good subsets.
2Using bit manipulation allows for efficient representation and counting of prime factors.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.