Given an array arr[] of size N. The task is to find a number of subsets whose product can be represented as a product of one or more distinct prime numbers. Modify your answer to the modulo of 109 + 7.

Example:

Input: N = 4, arr[] = {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.

Input: N = 3, arr[] =  {2, 2, 3}
Output: 5
Explanation: The good subsets are : {2}, {2}, {2, 3}, {2, 3}, {3}

Approach: This can be solved with the following idea:

The general approach for the given problem is to use dynamic programming to count the number of good subsets.

Below are the steps involved in the implementation of the code:

• Create a static array map with a size of 31, along with a constant mod of 109 + 7.
• Find the prime factors of each integer i from 2 to 30 and set the associated bits in map[i] if i is not a multiple of 4 or 9 or equal to 25.
• Set the first member of the integer array dp to 1 and initialize the integer variables one and cnt to have sizes of 1024 and 31, respectively  Step 4: If the appropriate map[i] value is non-zero and the integer i is not 1, increment one for each integer i in the provided array arr; otherwise, increment the count of i in the cnt array.
• For each index, i in the cnt array where the value is non-zero, iterate through all the possible subsets of prime numbers using a nested loop over all the possible j values from 0 to 1023. If the jth bit is set and the map[i]th bit is also set, skip to the next j. Otherwise, update the dp[j| map[i]] value with the sum of its current value and the product of the count of i and the dp[j] value.
• After the loops are complete, initialize a long variable res as 0, iterate through all the elements of the dp array, and update the res value as the sum of its current value and the current element’s value. Then decrement res by 1.
• If the one value is non-zero, calculate its power using a helper function pow and multiply the result with res. Finally, return the result as an i integer.

Below is the code implementation of the above method:

// Java code of the above approach
class Solution {

    static int mod = (int)1e9 + 7;

    static int[] map = new int[31];

    // Check for prime value
    static
    {
        int[] prime = new int[] { 2, 3, 5, 7, 11,
                                  13, 17, 19, 23, 29 };
        for (int i = 2; i <= 30; ++i) {

            // If num is a multiple of
            // 4/9/25, adding it to any
            // subset will make it bad
            if (0 == i % 4 || 0 == i % 9 || 25 == i)
                continue;
            int mask = 0;
            for (int j = 0; j < 10; ++j) {
                if (0 == i % prime[j])
                    mask |= 1 << j;
            }
            map[i] = mask;
        }
    }

    public int goodSubsets(int[] arr, int n)
    {

        int one = 0;

        // dp[set_of_primes] represents
        // the number of times set_of_primes
        // can be formed (set_of_primes ===
        // mask) Since there are 10 possible
        // prime numbers, there are 2^10
        // possible set_of_primes
        int[] dp = new int[1024], cnt = new int[31];
        dp[0] = 1;
        for (int i : arr) {
            if (i == 1)
                one++;
            else if (map[i] != 0)
                cnt[i]++;
        }
        for (int i = 0; i < 31; ++i) {
            if (cnt[i] == 0)
                continue;
            for (int j = 0; j < 1024; ++j) {
                if (0 != (j & map[i]))
                    continue;
                dp[j | map[i]]
                    = (int)((dp[j | map[i]]
                             + dp[j] * (long)cnt[i])
                            % mod);
            }
        }
        long res = 0;
        for (int i : dp)
            res = (res + i) % mod;
        res--;
        if (one != 0)
            res = res * pow(one) % mod;
        return (int)res;
    }

    // Function to calculate power
    public long pow(int n)
    {
        long res = 1, m = 2;
        while (n != 0) {
            if (1 == (n & 1))
                res = (res * m) % mod;
            m = m * m % mod;
            n >>= 1;
        }
        return res;
    }

    // Driver code
    public static void main(String[] args)
    {
        int[] arr = { 1, 2, 3, 4 };
        int n = arr.length;
        Solution solution = new Solution();

        // Function call
        int result = solution.goodSubsets(arr, n);

        System.out.println(result);
    }
}

6

Time Complexity: O(N*logN)
Auxiliary Space: O(N)