Count the Number of Square-Free Subsets
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 elements from nums (possibly none, but not all). Two subsets are different if and only if the chosen indices to delete are different.
Example 1
Input
nums = [3,4,4,5]Output
3There are exactly three square-free subsets:
[3], [5], and [3, 5].Example 2
Input
nums = [1]Output
1The only non-empty subset is
[1], whose product is 1, a square-free integer.Constraints
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 30
Asked at 2 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.