Count the Number of Square-Free Subsets

Hard
747.

Count the Number of Square-Free Subsets

Count the Number of Square-Free Subsets is a hard coding problem on dynamic programming, math and bit manipulation, asked in Amazon, Google and Uber interviews.

A number is square-free when no perfect square above 1 divides it. A subset of nums is square-free when the product of its elements is square-free.

Return the number of non-empty square-free subsets, modulo 10^9 + 7. Subsets are distinguished by the indices they use.

Example 1

Input
nums = [3,4,4,5]
Output
3
Explanation
The square-free subsets are {3}, {5} and {3,5} — 4 is divisible by 4.

Example 2

Input
nums = [1]
Output
1
Explanation
1 is square-free.

Example 3

Input
nums = [2,3,6]
Output
4
Explanation
{2}, {3}, {6} and {2,3}; pairing 6 with either factor repeats a prime.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 30
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var squareFreeSubsets = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count the Number of Square-Free Subsets — Problem & Solution

Count the Number of Square-Free Subsets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count the Number of Square-Free Subsets is a hard coding problem on dynamic programming, math and bit manipulation, asked in Amazon, Google and Uber interviews.

Problem statement

A number is square-free when no perfect square above 1 divides it. A subset of nums is square-free when the product of its elements is square-free.

Return the number of non-empty square-free subsets, modulo 10^9 + 7. Subsets are distinguished by the indices they use.

Example 1

Input: nums = [3,4,4,5]
Output: 3
Explanation: The square-free subsets are {3}, {5} and {3,5} — 4 is divisible by 4.

Example 2

Input: nums = [1]
Output: 1
Explanation: 1 is square-free.

Example 3

Input: nums = [2,3,6]
Output: 4
Explanation: {2}, {3}, {6} and {2,3}; pairing 6 with either factor repeats a prime.

Constraints

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 30

Hints for Count the Number of Square-Free Subsets

  1. Hint 1

    Values are at most 30, so only the ten primes below 30 can appear — encode each value as a 10-bit prime mask.

  2. Hint 2

    A value divisible by a square (4, 8, 9, 12, …) can never be used at all.

  3. Hint 3

    A subset is square-free exactly when the chosen masks are pairwise disjoint, which is a subset-sum DP over 1024 states.

How to solve Count the Number of Square-Free Subsets

A product is square-free precisely when no prime repeats, so each usable value becomes a set of primes and a valid subset is a collection of pairwise-disjoint sets. Counting those is a DP over the 1024 possible prime sets.

Approach

  1. For each value, build its prime mask, marking it unusable if any prime appears squared.
  2. Keep dp[mask], the number of subsets whose combined prime set is exactly mask, seeded with dp[0] = 1 for the empty subset.
  3. For each usable value, iterate the states downward and add dp[s] into dp[s | m] whenever s and m are disjoint.
  4. Sum all states and subtract 1 for the empty subset.

Why it works

Iterating the states in decreasing order is what stops a value from being used twice within one pass. The value 1 has an empty mask, so dp[s] += dp[s] doubles every count — exactly right, since each 1 may independently be included or left out.

Complexity

  • Time — O(n · 1024)
  • Space — O(1024)

Pitfalls

  • Forgetting to subtract the empty subset overcounts by one.
  • Treating 1 as unusable loses the factor of 2^(number of ones).
  • Iterating states upward lets a single element be chosen more than once.

Reference solution

Python

from typing import List

def squareFreeSubsets(nums: List[int]) -> int:
    MOD = 1000000007
    primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

    def mask_of(v: int) -> int:
        m = 0
        for i, p in enumerate(primes):
            if v % p == 0:
                if v % (p * p) == 0:
                    return -1
                m |= 1 << i
        return m

    dp = [0] * 1024
    dp[0] = 1
    for v in nums:
        m = mask_of(v)
        if m < 0:
            continue
        for s in range(1023, -1, -1):
            if dp[s] and not (s & m):
                dp[s | m] = (dp[s | m] + dp[s]) % MOD
    return (sum(dp) - 1) % MOD

Java

public static int squareFreeSubsets(int[] nums) {
    final long MOD = 1000000007L;
    int[] primes = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
    long[] dp = new long[1024];
    dp[0] = 1;
    for (int v : nums) {
        int m = 0;
        boolean ok = true;
        for (int i = 0; i < 10 && ok; i++) {
            int p = primes[i];
            if (v % p == 0) {
                if (v % (p * p) == 0) ok = false;
                else m |= 1 << i;
            }
        }
        if (!ok) continue;
        for (int s = 1023; s >= 0; s--) {
            if (dp[s] == 0 || (s & m) != 0) continue;
            dp[s | m] = (dp[s | m] + dp[s]) % MOD;
        }
    }
    long total = 0;
    for (long v : dp) total = (total + v) % MOD;
    return (int) ((total - 1 + MOD) % MOD);
}

C++

int squareFreeSubsets(vector<int>& nums) {
    const long long MOD = 1000000007LL;
    int primes[10] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 };
    vector<long long> dp(1024, 0);
    dp[0] = 1;
    for (int v : nums) {
        int m = 0;
        bool ok = true;
        for (int i = 0; i < 10 && ok; i++) {
            int p = primes[i];
            if (v % p == 0) {
                if (v % (p * p) == 0) ok = false;
                else m |= 1 << i;
            }
        }
        if (!ok) continue;
        for (int s = 1023; s >= 0; s--) {
            if (dp[s] == 0 || (s & m) != 0) continue;
            dp[s | m] = (dp[s | m] + dp[s]) % MOD;
        }
    }
    long long total = 0;
    for (long long v : dp) total = (total + v) % MOD;
    return (int) ((total - 1 + MOD) % MOD);
}

JavaScript

var squareFreeSubsets = function(nums) {
    var MOD = 1000000007;
    var primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29];
    var maskOf = function(v) {
        var m = 0;
        for (var i = 0; i < primes.length; i++) {
            var p = primes[i];
            if (v % p === 0) {
                if (v % (p * p) === 0) return -1;
                m |= 1 << i;
            }
        }
        return m;
    };
    var dp = [];
    for (var t = 0; t < 1024; t++) dp.push(0);
    dp[0] = 1;
    for (var j = 0; j < nums.length; j++) {
        var m = maskOf(nums[j]);
        if (m < 0) continue;
        for (var s = 1023; s >= 0; s--) {
            if (dp[s] === 0) continue;
            if ((s & m) !== 0) continue;
            dp[s | m] = (dp[s | m] + dp[s]) % MOD;
        }
    }
    var total = 0;
    for (var u = 0; u < 1024; u++) total = (total + dp[u]) % MOD;
    return (total - 1 + MOD) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 402 dynamic programming problems · the whole catalogue

Learn the technique: Dynamic Programming · Bit Manipulation