Count the Number of Square-Free Subsets - Practice Coding Problems

Count the Number of Square-Free Subsets - Problem

You are given a positive integer 0-indexed array nums.

A subset of the array nums is square-free if the product of its elements is a square-free integer.

A square-free integer is an integer that is divisible by no square number other than 1.

Return the number of square-free non-empty subsets of the array nums. Since the answer may be too large, return it modulo 10^9 + 7.

A non-empty subset of nums is an array that can be obtained by deleting some (possibly none but not 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 = [3,4,4,5]

› Output: 3

💡 Note: Square-free subsets are [3], [4], [5]. Note that [4,4] has product 16 = 4², so it's not square-free. [3,4], [3,5], [4,5] would work but [3,4,4] and others with 4,4 don't.

Example 2 — All Valid

$ Input: nums = [1]

› Output: 1

💡 Note: Only subset is [1], and 1 is square-free (no square factors other than 1).

Example 3 — Prime Numbers

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

› Output: 7

💡 Note: All 7 non-empty subsets work: [2], [3], [5], [2,3], [2,5], [3,5], [2,3,5]. Products are 2,3,5,6,10,15,30 - all square-free.

Constraints

1 ≤ nums.length ≤ 1000
1 ≤ nums[i] ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input Analysis

Array [3,4,4,5] with prime factors

Square-Free Check

Products must have no repeated prime factors

Count Result

Valid subsets: [3], [4], [5]

Key Takeaway

🎯 Key Insight: A subset is square-free if no prime factor appears with even total power across all elements

Asked in

G Google 15 M Microsoft 12 a Amazon 8

The key insight is representing each number by its prime factors as a bitmask - a square-free subset means no prime factor appears more than once across all numbers. Best approach uses Dynamic Programming with bitmasks to count valid combinations efficiently. Time: O(n × 2^k), Space: O(2^k) where k ≤ 10.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Memoization	O(n × 2^k)	O(n × 2^k)	Use recursion with memoization to count square-free subsets for each prime factor state
Dynamic Programming with Prime Factorization	O(n × 2^k)	O(2^k)	Use DP with prime factor bitmasks to count square-free subsets efficiently
Brute Force	O(2^n × √max_product)	O(1)	Generate all subsets and check if their product is square-free

Recursive Memoization — Algorithm Steps

Convert each number to its prime factor representation
Use recursion: for each number, try include/exclude decisions
Memoize results based on current index and prime factor mask state

Visualization

Tap to expand

Step-by-Step Walkthrough

Decision Tree

For each number, decide include/exclude

State Memoization

Cache results by (index, prime_mask) state

Combine Results

Sum all valid paths minus empty subset

Code -

solution.c — C

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

#define MOD 1000000007
#define MAXN 1000
#define HASH_SIZE 100000

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

typedef struct HashNode {
    char key[50];
    long long value;
    struct HashNode* next;
} HashNode;

HashNode* hashTable[HASH_SIZE];

int hash(const char* key) {
    int h = 0;
    for (int i = 0; key[i]; i++) {
        h = (h * 31 + key[i]) % HASH_SIZE;
    }
    return h;
}

long long getMemo(const char* key) {
    int h = hash(key);
    HashNode* node = hashTable[h];
    while (node) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return -1;
}

void setMemo(const char* key, long long value) {
    int h = hash(key);
    HashNode* node = (HashNode*)malloc(sizeof(HashNode));
    strcpy(node->key, key);
    node->value = value;
    node->next = hashTable[h];
    hashTable[h] = node;
}

int getPrimeMask(int n) {
    int mask = 0;
    for (int i = 0; i < primesSize; i++) {
        int cnt = 0;
        while (n % primes[i] == 0) {
            n /= primes[i];
            cnt++;
        }
        if (cnt % 2 == 1) {
            mask |= (1 << i);
        }
    }
    return n == 1 ? mask : -1;
}

long long dfs(int* validNums, int validSize, int idx, int currentMask) {
    if (idx == validSize) {
        return 1;
    }
    
    char key[50];
    sprintf(key, "%d,%d", idx, currentMask);
    
    long long cached = getMemo(key);
    if (cached != -1) {
        return cached;
    }
    
    long long result = dfs(validNums, validSize, idx + 1, currentMask);
    
    if ((currentMask & validNums[idx]) == 0) {
        result = (result + dfs(validNums, validSize, idx + 1, currentMask | validNums[idx])) % MOD;
    }
    
    setMemo(key, result);
    return result;
}

int solution(int* nums, int numsSize) {
    int validNums[MAXN];
    int validSize = 0;
    
    for (int i = 0; i < numsSize; i++) {
        int mask = getPrimeMask(nums[i]);
        if (mask != -1) {
            validNums[validSize++] = mask;
        }
    }
    
    long long result = dfs(validNums, validSize, 0, 0) - 1;
    return (result + MOD) % MOD;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int nums[MAXN];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    
    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^k)

Each of n positions can be in 2^k different prime factor states, each computed once due to memoization

✓ Linear Growth

Space Complexity

O(n × 2^k)

Memoization table stores results for each (index, mask) combination plus recursion call stack

⚡ Linearithmic Space

12.0K Views

Medium Frequency

~35 min Avg. Time

456 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

Recursive Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler