How hard is LeetCode 1994. The Number of Good Subsets?

LeetCode 1994. The Number of Good Subsets is rated Hard on LeetCode.

What is the time complexity of LeetCode 1994. The Number of Good Subsets?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 1994. The Number of Good Subsets?

The Python solution on this page uses O(n) auxiliary space.

The Number of Good Subsets — LeetCode 1994 Python Solution

HardBit ManipulationArrayHash TableMathDynamic ProgrammingBitmaskCountingNumber Theory

Problem: #1994
Pattern: Bit Manipulation
Reading time: 4 min
Source: leetcode.com

The problem

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.

Example

Input: nums = [1,2,3,4]
Output: 6
Explanation: The good subsets are:

Python solution

Python

class Solution:
    def numberOfGoodSubsets(self, nums: List[int]) -> int:
        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
        cnt = Counter(nums)
        mod = 10**9 + 7
        n = len(primes)
        f = [0] * (1 << n)
        f[0] = pow(2, cnt[1])
        for x in range(2, 31):
            if cnt[x] == 0 or x % 4 == 0 or x % 9 == 0 or x % 25 == 0:
                continue
            mask = 0
            for i, p in enumerate(primes):
                if x % p == 0:
                    mask |= 1 << i
            for state in range((1 << n) - 1, 0, -1):
                if state & mask == mask:
                    f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod
        return sum(f[i] for i in range(1, 1 << n)) % mod

Complexity

Measure	Complexity
Time	O(n)
Space	O(n) auxiliary

Pattern: Bit Manipulation

Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 1994. The Number of Good Subsets is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.

The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1994. The Number of Good Subsets?: LeetCode 1994. The Number of Good Subsets is rated Hard on LeetCode.
What is the time complexity of LeetCode 1994. The Number of Good Subsets?: The Python solution on this page runs in O(n).
What is the space complexity of LeetCode 1994. The Number of Good Subsets?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1994. The Number of Good Subsets cover?: LeetCode 1994. The Number of Good Subsets is tagged Bit Manipulation, Array, Hash Table, Math, Dynamic Programming, Bitmask, Counting and Number Theory on LeetCode.