LeetCode 1994 - The Number of Good Subsets

This problem asks us to count how many subsets of the input array have a product that can be written as a multiplication of distinct prime numbers. The phrase "distinct prime numbers" is the key restriction.

leetcodehardarrayhash-tablemathdynamic-programmingbit-manipulationcountingnumber-theorybitmask

LeetCode Problem 1994

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Dynamic Programming, Bit Manipulation, Counting, Number Theory, Bitmask

Solution

LeetCode 1994 - The Number of Good Subsets

Problem Understanding

This problem asks us to count how many subsets of the input array have a product that can be written as a multiplication of distinct prime numbers.

The phrase "distinct prime numbers" is the key restriction. A product is valid only if no prime factor appears more than once in the final product.

For example:

  • 6 = 2 × 3 is valid because both primes are distinct.
  • 30 = 2 × 3 × 5 is valid for the same reason.
  • 12 = 2 × 2 × 3 is invalid because the prime 2 appears twice.
  • 4 = 2 × 2 is invalid because the same prime is repeated.

The input array may contain duplicate values, and subsets are distinguished by indices, not values. That means if the array contains two copies of 2, choosing the first one is considered different from choosing the second one.

The constraints are important:

  • nums.length can be as large as 10^5
  • Every number is between 1 and 30

The large array size means exponential subset enumeration is impossible. However, the small numeric range from 1 to 30 is extremely important because it allows us to preprocess all possible values.

The number 1 is a special case. It has no prime factors, so it does not affect whether a subset is good. Any good subset can include any number of 1s without changing the product structure.

Another important observation is that numbers containing repeated prime factors can never appear in a good subset. Examples include:

  • 4 = 2²
  • 8 = 2³
  • 9 = 3²
  • 12 = 2² × 3

Such numbers are automatically invalid because they already contain repeated primes internally.

The valid numbers between 1 and 30 are therefore only those whose prime factorization contains no repeated primes.

Important edge cases include:

  • Arrays containing only 1s
  • Arrays containing only invalid numbers like 4, 8, 9
  • Large numbers of duplicates
  • Situations where combining two individually valid numbers creates a repeated prime factor conflict

Approaches

Brute Force Approach

The brute force solution is to generate every possible subset and check whether its product is a product of distinct primes.

For each subset:

  1. Compute the product
  2. Factorize the product
  3. Verify that every prime factor appears exactly once

This approach is correct because it directly follows the definition of a good subset.

However, the time complexity is catastrophic. An array of length n has 2^n subsets. Since n can be 100000, brute force is completely infeasible.

Even with optimizations, subset enumeration cannot work for these constraints.

Key Insight

The most important observation is that values are limited to the range [1, 30].

There are only 10 primes less than or equal to 30:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29

A good subset can therefore be represented by which of these primes are already used.

This naturally suggests a bitmask dynamic programming solution.

Each valid number can be converted into a bitmask representing its prime factors.

For example:

  • 2 → 0000000001
  • 3 → 0000000010
  • 6 → 0000000011
  • 15 → 0000000110

If two numbers share a prime factor, their masks overlap:

(maskA & maskB) != 0

This lets us efficiently determine whether two numbers can coexist in the same good subset.

Instead of iterating over subsets of array indices, we iterate over combinations of prime masks.

Because there are only 2^10 = 1024 possible masks, the state space becomes very manageable.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n × n) O(n) Enumerates every subset and checks validity
Optimal O(30 × 2^10) O(2^10) Bitmask DP using prime factor states

Algorithm Walkthrough

Step 1: Count the frequency of every number

Since values are only from 1 to 30, we first count how many times each value appears.

This lets us process each distinct number once instead of repeatedly iterating through duplicates.

Step 2: Define the prime list

The relevant primes are:

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Each prime corresponds to one bit in a 10-bit mask.

Step 3: Build masks for valid numbers

For each number from 2 to 30:

  1. Determine its prime factorization
  2. If any prime appears more than once, discard the number
  3. Otherwise, create a bitmask representing its distinct prime factors

For example:

  • 10 = 2 × 5

  • mask = 0000000101

  • 14 = 2 × 7

  • mask = 0000001001

Invalid numbers like 12 = 2² × 3 are skipped.

Step 4: Initialize DP

We create a DP array of size 1024.

dp[mask]

represents the number of ways to create a subset whose used prime set equals mask.

Initially:

dp[0] = 1

This represents the empty subset.

Step 5: Process each valid number

For every valid number:

  1. Get its mask
  2. Iterate through all existing masks in reverse order
  3. If the current mask does not overlap:
(existing_mask & current_mask) == 0
  1. Update the combined state

The reverse iteration prevents reusing the same number multiple times in one update cycle.

If a number appears k times, then there are k ways to choose one occurrence.

So the transition becomes:

dp[new_mask] += dp[old_mask] × frequency

Step 6: Handle the number 1

The number 1 contributes no prime factors.

Every good subset can independently choose to include or exclude each 1.

If there are c ones, then each valid subset can be multiplied by:

2^c

because every 1 has two choices:

  • included
  • excluded

Step 7: Compute the final answer

Sum all nonzero masks:

sum(dp[1:])

Then multiply by:

2^(count_of_1)

Finally, apply modulo 10^9 + 7.

Why it works

The DP invariant is:

dp[mask]

always stores the number of subsets whose combined prime factors exactly equal mask, with no repeated primes.

Because every valid number itself contains distinct primes, and we only combine masks with no overlap, every constructed subset remains valid.

Conversely, every good subset corresponds to exactly one sequence of valid transitions, so all good subsets are counted exactly once.

Python Solution

from typing import List
from collections import Counter

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        
        count = Counter(nums)
        
        masks = {}
        
        for num in range(2, 31):
            x = num
            mask = 0
            valid = True
            
            for i, prime in enumerate(primes):
                prime_count = 0
                
                while x % prime == 0:
                    x //= prime
                    prime_count += 1
                
                if prime_count > 1:
                    valid = False
                    break
                
                if prime_count == 1:
                    mask |= (1 << i)
            
            if valid:
                masks[num] = mask
        
        dp = [0] * (1 << 10)
        dp[0] = 1
        
        for num in range(2, 31):
            if num not in masks or count[num] == 0:
                continue
            
            current_mask = masks[num]
            frequency = count[num]
            
            for existing_mask in range((1 << 10) - 1, -1, -1):
                if existing_mask & current_mask:
                    continue
                
                new_mask = existing_mask | current_mask
                
                dp[new_mask] = (
                    dp[new_mask]
                    + dp[existing_mask] * frequency
                ) % MOD
        
        result = sum(dp[1:]) % MOD
        
        ones = count[1]
        result = (result * pow(2, ones, MOD)) % MOD
        
        return result

The implementation begins by counting the occurrences of every number. This is important because duplicates are handled through multiplication by frequency instead of repeated processing.

The masks dictionary stores the prime-factor bitmask for every valid number. During construction, the code factorizes each number and rejects any number containing repeated prime factors.

The DP array has size 1024, corresponding to all possible subsets of the 10 primes.

The transition step iterates backward through masks to avoid double-counting within the same iteration. Whenever two masks have no overlap, they can safely combine into a larger valid subset.

Finally, all non-empty valid masks are summed, and the contribution from 1s is applied using modular exponentiation.

Go Solution

package main

func numberOfGoodSubsets(nums []int) int {
	const MOD int = 1e9 + 7

	primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

	count := make([]int, 31)

	for _, num := range nums {
		count[num]++
	}

	masks := make([]int, 31)
	valid := make([]bool, 31)

	for num := 2; num <= 30; num++ {
		x := num
		mask := 0
		ok := true

		for i, prime := range primes {
			primeCount := 0

			for x%prime == 0 {
				x /= prime
				primeCount++
			}

			if primeCount > 1 {
				ok = false
				break
			}

			if primeCount == 1 {
				mask |= (1 << i)
			}
		}

		if ok {
			valid[num] = true
			masks[num] = mask
		}
	}

	dp := make([]int, 1<<10)
	dp[0] = 1

	for num := 2; num <= 30; num++ {
		if !valid[num] || count[num] == 0 {
			continue
		}

		currentMask := masks[num]
		frequency := count[num]

		for existingMask := (1 << 10) - 1; existingMask >= 0; existingMask-- {
			if existingMask&currentMask != 0 {
				continue
			}

			newMask := existingMask | currentMask

			dp[newMask] = (dp[newMask] +
				dp[existingMask]*frequency) % MOD
		}
	}

	result := 0

	for mask := 1; mask < (1 << 10); mask++ {
		result = (result + dp[mask]) % MOD
	}

	pow2 := 1
	for i := 0; i < count[1]; i++ {
		pow2 = (pow2 * 2) % MOD
	}

	result = (result * pow2) % MOD

	return result
}

The Go implementation follows the same logic as the Python version. Arrays are used instead of dictionaries where possible because the numeric range is fixed and small.

Since Go does not provide built-in modular exponentiation for integers, the power of two for the 1s is computed manually with repeated multiplication.

The DP array uses integer arithmetic safely because all operations are reduced modulo 10^9 + 7.

Worked Examples

Example 1

nums = [1,2,3,4]

Step 1: Frequency Count

Number Count
1 1
2 1
3 1
4 1

Step 2: Build Masks

Number Prime Factors Valid Mask
2 2 Yes 0000000001
3 3 Yes 0000000010
4 2² No skipped

Step 3: DP Updates

Initial:

Mask Value
0000000000 1

Process 2:

New Mask Value
0000000001 1

Process 3:

New Mask Value
0000000010 1
0000000011 1

Final DP states:

Mask Subset
0000000001 [2]
0000000010 [3]
0000000011 [2,3]

Total before ones:

3

There is one 1, so multiply by:

2^1 = 2

Final answer:

3 × 2 = 6

Example 2

nums = [4,2,3,15]

Step 1: Frequency Count

Number Count
2 1
3 1
4 1
15 1

Step 2: Valid Numbers

Number Prime Factors Valid Mask
2 2 Yes 0000000001
3 3 Yes 0000000010
4 2² No skipped
15 3×5 Yes 0000000110

Step 3: DP Processing

After 2:

Mask Count
0000000001 1

After 3:

Mask Count
0000000010 1
0000000011 1

After 15:

15 conflicts with masks already containing prime 3.

Allowed combinations:

  • empty + 15
  • 2 + 15

Final subsets:

Subset
[2]
[3]
[2,3]
[15]
[2,15]

Answer:

5

Complexity Analysis

Measure Complexity Explanation
Time O(30 × 2^10) Each valid number processes all mask states
Space O(2^10) DP array stores all prime-mask combinations

The complexity is effectively constant relative to n because the value range is capped at 30.

Counting frequencies takes O(n), but the DP itself only processes at most 30 numbers and 1024 states.

This is why the solution easily handles arrays of length 100000.

Test Cases

from typing import List

s = Solution()

assert s.numberOfGoodSubsets([1,2,3,4]) == 6
# basic example with one invalid square number

assert s.numberOfGoodSubsets([4,2,3,15]) == 5
# example containing invalid and valid composites

assert s.numberOfGoodSubsets([1,1,1]) == 0
# only ones, no non-empty good subset possible

assert s.numberOfGoodSubsets([2]) == 1
# single prime

assert s.numberOfGoodSubsets([4]) == 0
# invalid square number alone

assert s.numberOfGoodSubsets([2,2]) == 2
# duplicates count as different index subsets

assert s.numberOfGoodSubsets([2,3,5]) == 7
# all non-empty subsets are valid

assert s.numberOfGoodSubsets([6,10,15]) == 3
# pairwise conflicts prevent combining

assert s.numberOfGoodSubsets([1,2,2,3]) == 12
# ones multiply all valid subsets

assert s.numberOfGoodSubsets([8,9,16,25]) == 0
# all invalid due to repeated prime factors

assert s.numberOfGoodSubsets([30]) == 1
# product with many distinct primes

assert s.numberOfGoodSubsets([2,6]) == 2
# cannot combine because both contain prime 2
Test Why
[1,2,3,4] Verifies sample behavior
[4,2,3,15] Tests invalid square handling
[1,1,1] Ensures pure ones produce zero
[2] Smallest valid subset
[4] Smallest invalid subset
[2,2] Confirms duplicate index counting
[2,3,5] All subsets valid
[6,10,15] Tests overlapping prime conflicts
[1,2,2,3] Verifies multiplication by ones
[8,9,16,25] All numbers invalid
[30] Multiple distinct primes in one number
[2,6] Shared prime conflict

Edge Cases

One important edge case is when the array contains only 1s. Since 1 contributes no prime factors, there must still be at least one non-one number to form a good subset. A naive implementation might incorrectly count subsets of only 1s as valid. This solution avoids that by summing only nonzero masks before multiplying by powers of two.

Another important case is numbers containing repeated prime factors internally, such as 4, 8, 9, or 12. These numbers are invalid even before considering interactions with other numbers. The preprocessing step explicitly factorizes each number and rejects any number where a prime appears more than once.

A third tricky case is when two individually valid numbers cannot coexist because they share a prime factor. For example, 6 = 2×3 and 10 = 2×5 are each valid independently, but cannot both appear in the same subset because prime 2 would repeat. The bitmask overlap check:

(existing_mask & current_mask) != 0

guarantees such combinations are excluded.

Another subtle case is duplicate values. If the array contains multiple copies of a number, subsets using different indices are considered distinct. The frequency multiplication in the DP transition correctly accounts for this without explicitly enumerating duplicate subsets.