The Number of Good Subsets - Practice Coding Problems

The Number of Good Subsets - Problem

Array Hash Table Math Dynamic Programming Bit Manipulation Counting Number Theory Bitmask Hard

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 = 2*3, 6 = 2*3, and 3 = 3 respectively.
[1, 4] and [4] are not good subsets with products 4 = 2*2 and 4 = 2*2 respectively.

Return the number of different good subsets in nums modulo 10⁹ + 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.

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,3,4]

› Output: 6

💡 Note: Good subsets: [2], [3], [1,2], [1,3], [2,3], [1,2,3]. The subsets [4], [1,4], [2,4], [3,4], [1,2,4], [1,3,4], [2,3,4], [1,2,3,4] are not good because 4 = 2² contains repeated prime factor 2.

Example 2 — Only Prime Numbers

$ Input: nums = [2,3,5]

› Output: 7

💡 Note: All non-empty subsets are good: [2], [3], [5], [2,3], [2,5], [3,5], [2,3,5]. Each contains only distinct prime factors.

Example 3 — Contains Invalid Numbers

$ Input: nums = [4,2,1]

› Output: 3

💡 Note: Good subsets: [2], [1,2], [1]. Number 4 = 2² cannot be in any good subset due to repeated prime factor.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 30

Visualization

Tap to expand

Understanding the Visualization

Input Array

Given array [1,2,3,4] with mixed valid/invalid numbers

Prime Analysis

Check each number's prime factorization for uniqueness

Count Good Subsets

Return count of all valid combinations

Key Takeaway

🎯 Key Insight: Only numbers ≤ 30 with distinct prime factors can form good subsets, making bitmask DP highly efficient

Asked in

M Meta 3 G Google 2

The key insight is that only numbers ≤ 30 with distinct prime factors matter, and we can use bitmask DP to efficiently track which primes are used. Best approach uses bitmask dynamic programming with Time: O(n + 2¹⁰), Space: O(2¹⁰).

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming with Bitmask	O(n + 2^10)	O(2^10)	Use bitmask DP to track which primes are used, only consider numbers ≤ 30
Brute Force - Generate All Subsets	O(2^n × k)	O(k)	Generate all 2^n subsets and check each for distinct prime factors

Dynamic Programming with Bitmask — Algorithm Steps

Filter numbers ≤ 30 with distinct prime factors
Create bitmask for each valid number's primes
Use DP: dp[mask] = ways to achieve this prime combination
Handle 1's separately (can be added to any subset)

Visualization

Tap to expand

Step-by-Step Walkthrough

Filter Valid Numbers

Only keep numbers ≤30 with distinct prime factors

Create Bitmasks

Each number gets a bitmask representing its primes

DP Transition

Combine non-overlapping prime sets

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

long long modPow(long long base, int exp, int mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int solution(int* nums, int numsSize) {
    const int MOD = 1000000007;
    int primes[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
    int primesSize = 10;
    
    // Precompute valid numbers and their masks
    int validMasks[31];
    bool isValid[31];
    memset(isValid, false, sizeof(isValid));
    
    for (int num = 2; num <= 30; num++) {
        int temp = num;
        int mask = 0;
        bool valid = true;
        
        for (int i = 0; i < primesSize; i++) {
            int count = 0;
            while (temp % primes[i] == 0) {
                temp /= primes[i];
                count++;
            }
            if (count > 1) {
                valid = false;
                break;
            }
            if (count == 1) {
                mask |= (1 << i);
            }
        }
        
        if (valid && temp == 1) {
            validMasks[num] = mask;
            isValid[num] = true;
        }
    }
    
    // Count frequencies
    int count[10001] = {0};
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] <= 10000) count[nums[i]]++;
    }
    int ones = count[1];
    
    // DP
    long long dp[1024] = {0};
    dp[0] = 1;
    
    for (int num = 2; num <= 30; num++) {
        if (!isValid[num] || count[num] == 0) continue;
        
        int mask = validMasks[num];
        int freq = count[num];
        
        long long newDp[1024];
        memcpy(newDp, dp, sizeof(dp));
        
        for (int prevMask = 0; prevMask < 1024; prevMask++) {
            if (dp[prevMask] == 0) continue;
            if ((prevMask & mask) == 0) {
                int newMask = prevMask | mask;
                newDp[newMask] = (newDp[newMask] + dp[prevMask] * freq) % MOD;
            }
        }
        memcpy(dp, newDp, sizeof(dp));
    }
    
    long long result = 0;
    for (int i = 1; i < 1024; i++) {
        result = (result + dp[i]) % MOD;
    }
    
    if (ones > 0) {
        long long power = modPow(2, ones, MOD);
        result = (result * power) % MOD;
    }
    
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[1000];
    int numsSize = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token != NULL) {
            nums[numsSize++] = atoi(token);
            token = strtok(NULL, ",]");
        }
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + 2^10)

O(n) to count frequencies, O(2^10) for DP since only 10 primes ≤ 30

✓ Linear Growth

Space Complexity

O(2^10)

DP array of size 2^10 = 1024 for all prime combinations

✓ Linear Space

28.0K Views

Medium Frequency

~35 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming with Bitmask — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler