The Number of Good Subsets

// Accepted solution for LeetCode #1994: The Number of Good Subsets
class Solution {
    public int numberOfGoodSubsets(int[] nums) {
        int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
        int[] cnt = new int[31];
        for (int x : nums) {
            ++cnt[x];
        }
        final int mod = (int) 1e9 + 7;
        int n = primes.length;
        long[] f = new long[1 << n];
        f[0] = 1;
        for (int i = 0; i < cnt[1]; ++i) {
            f[0] = (f[0] * 2) % mod;
        }
        for (int x = 2; x < 31; ++x) {
            if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
                continue;
            }
            int mask = 0;
            for (int i = 0; i < n; ++i) {
                if (x % primes[i] == 0) {
                    mask |= 1 << i;
                }
            }
            for (int state = (1 << n) - 1; state > 0; --state) {
                if ((state & mask) == mask) {
                    f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod;
                }
            }
        }
        long ans = 0;
        for (int i = 1; i < 1 << n; ++i) {
            ans = (ans + f[i]) % mod;
        }
        return (int) ans;
    }
}

// Accepted solution for LeetCode #1994: The Number of Good Subsets
func numberOfGoodSubsets(nums []int) (ans int) {
	primes := []int{2, 3, 5, 7, 11, 13, 17, 19, 23, 29}
	cnt := [31]int{}
	for _, x := range nums {
		cnt[x]++
	}
	const mod int = 1e9 + 7
	n := 10
	f := make([]int, 1<<n)
	f[0] = 1
	for i := 0; i < cnt[1]; i++ {
		f[0] = f[0] * 2 % mod
	}
	for x := 2; x < 31; x++ {
		if cnt[x] == 0 || x%4 == 0 || x%9 == 0 || x%25 == 0 {
			continue
		}
		mask := 0
		for i, p := range primes {
			if x%p == 0 {
				mask |= 1 << i
			}
		}
		for state := 1<<n - 1; state > 0; state-- {
			if state&mask == mask {
				f[state] = (f[state] + f[state^mask]*cnt[x]) % mod
			}
		}
	}
	for i := 1; i < 1<<n; i++ {
		ans = (ans + f[i]) % mod
	}
	return
}

# Accepted solution for LeetCode #1994: The Number of Good Subsets
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

// Accepted solution for LeetCode #1994: The Number of Good Subsets
/**
 * [1994] The Number of Good Subsets
 *
 * 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^9 + 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.
 *  
 * Example 1:
 *
 * Input: nums = [1,2,3,4]
 * Output: 6
 * Explanation: The good subsets are:
 * - [1,2]: product is 2, which is the product of distinct prime 2.
 * - [1,2,3]: product is 6, which is the product of distinct primes 2 and 3.
 * - [1,3]: product is 3, which is the product of distinct prime 3.
 * - [2]: product is 2, which is the product of distinct prime 2.
 * - [2,3]: product is 6, which is the product of distinct primes 2 and 3.
 * - [3]: product is 3, which is the product of distinct prime 3.
 *
 * Example 2:
 *
 * Input: nums = [4,2,3,15]
 * Output: 5
 * Explanation: The good subsets are:
 * - [2]: product is 2, which is the product of distinct prime 2.
 * - [2,3]: product is 6, which is the product of distinct primes 2 and 3.
 * - [2,15]: product is 30, which is the product of distinct primes 2, 3, and 5.
 * - [3]: product is 3, which is the product of distinct prime 3.
 * - [15]: product is 15, which is the product of distinct primes 3 and 5.
 *
 *  
 * Constraints:
 *
 * 	1 <= nums.length <= 10^5
 * 	1 <= nums[i] <= 30
 *
 */
pub struct Solution {}

// problem: https://leetcode.com/problems/the-number-of-good-subsets/
// discuss: https://leetcode.com/problems/the-number-of-good-subsets/discuss/?currentPage=1&orderBy=most_votes&query=

// submission codes start here

impl Solution {
    pub fn number_of_good_subsets(nums: Vec<i32>) -> i32 {
        0
    }
}

// submission codes end

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    #[ignore]
    fn test_1994_example_1() {
        let nums = vec![1, 2, 3, 4];

        let result = 6;

        assert_eq!(Solution::number_of_good_subsets(nums), result);
    }

    #[test]
    #[ignore]
    fn test_1994_example_2() {
        let nums = vec![4, 2, 3, 15];

        let result = 5;

        assert_eq!(Solution::number_of_good_subsets(nums), result);
    }
}

// Accepted solution for LeetCode #1994: The Number of Good Subsets
// Auto-generated TypeScript example from java.
function exampleSolution(): void {
}
// Reference (java):
// // Accepted solution for LeetCode #1994: The Number of Good Subsets
// class Solution {
//     public int numberOfGoodSubsets(int[] nums) {
//         int[] primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
//         int[] cnt = new int[31];
//         for (int x : nums) {
//             ++cnt[x];
//         }
//         final int mod = (int) 1e9 + 7;
//         int n = primes.length;
//         long[] f = new long[1 << n];
//         f[0] = 1;
//         for (int i = 0; i < cnt[1]; ++i) {
//             f[0] = (f[0] * 2) % mod;
//         }
//         for (int x = 2; x < 31; ++x) {
//             if (cnt[x] == 0 || x % 4 == 0 || x % 9 == 0 || x % 25 == 0) {
//                 continue;
//             }
//             int mask = 0;
//             for (int i = 0; i < n; ++i) {
//                 if (x % primes[i] == 0) {
//                     mask |= 1 << i;
//                 }
//             }
//             for (int state = (1 << n) - 1; state > 0; --state) {
//                 if ((state & mask) == mask) {
//                     f[state] = (f[state] + cnt[x] * f[state ^ mask]) % mod;
//                 }
//             }
//         }
//         long ans = 0;
//         for (int i = 1; i < 1 << n; ++i) {
//             ans = (ans + f[i]) % mod;
//         }
//         return (int) ans;
//     }
// }