Unit Power Subsets

Hard
0/120
profile
Contributed by
2 upvotes

Problem statement

You are given an integer array ‘Arr’. You are required to calculate the number of subsets whose product can be represented as the product of unit powers of one or more distinct primes. As the answer can be large calculate it modulo (10^9+7).

Note: Subsets are considered distinct if the chosen set of indexes are different. For Example: 
Suppose arr = [1, 3, 9, 5]

Valid subsets are as follows:
[3], Product = 3.
[1, 3], Product = 1 * 3.
[5], Product = 5.
[1, 5], Product = 1 * 5.
[3, 5], Product = 3 * 5.
[1, 3, 5], Product = 1 * 3 * 5.
All of the above subsets’ products can be represented only with unit powers of prime and have at least one prime in their product. Hence they are valid. As we have six valid subsets, our output will be 6.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of the input contains a single integer ‘T’ representing the no. of test cases.

The first line of each test case contains a single integer ‘N’, denoting the size of ‘Arr’.

The second line of each test case contains ‘N’ space-separated integers, denoting the elements of ‘Arr’.

Output Format:

For each test case, print a single integer value denoting the number of valid subsets modulo (10^9+7).

Print a separate line for each test case.
Note: 
You are not required to print anything; it has already been taken care of. Just implement the function and return the answer.

Constraints:

1 ≤ T ≤ 1000
1 ≤ N ≤ 10^5
1 ≤ Arr[i] ≤ 20
1 ≤ ΣN ≤ 2 * 10^5

Time limit: 1 Sec
Sample Input 1 :
2
4
1 3 9 5
3
14 15 2
Sample Output 1 :
6
5
Explanation For Sample Input 1 :
For First Case - Same as explained in above example.

For the second case - 

arr = [14, 15, 2]
[14], Product = 2 * 7.
[15], Product = 3 * 5.
[2], Product = 2.
[14, 15], Product = 2 * 3 * 5 * 7.
[2, 15], Product = 2 * 3 * 5.
All of the above subsets’ products can be represented only with unit powers of prime and have at least one prime in their product. Hence they are valid. As we have five valid subsets, our output will be 6.
Sample Input 2 :
2
7
1 2 3 4 5 6 7
8
1 5 2 8 1 7 1 9
Sample Output 2 :
38
56
Hint

Can we check for all possible subsets of Arr?

Approaches (2)
Brute Force (Recursion)

We can recursively generate all the possible subsets of Arr and for each subset we can check whether its product can be expressed as product of unit powers of one or more primes. Implementation details will be as per the following algorithm.

 

Algorithm:


Check Function

Function arguments - integer array ‘subset’ to check for validity.

Returns boolean value whether the given subset is valid.

  • Declare frequency map primeFactors.
  • Iterate over all elements i of subset
    • Declare integer limit = squareRoot(i)
    • Iterate over j from 2 to limit
      • While i > 0 AND i is divisible by j
        • Divide i by j
        • Increment primeFactors[j]
    • If i > 1
      • Increment primeFactors[i]
  • For every frequency x in primeFactors
    • If x > 1
      • Return false
  • Return true if (primeFactors is not empty) and false otherwise.

 

Subsets Function

Function arguments - integer array ‘arr’, integer array ‘subset’ to maintain current subset, 64Bit integer ‘ans, integer value ‘ind’

Generates all subsets of arr and check them for validity.

  • If ind == size of options
    • Incement ans by check(subset)
    • Return
  • subsets(arr, subset, ans, ind+1)
  • Append options[ind[ to subset
  • subsets(arr, subset, ans, ind+1)
  • Remove the last element from the subset

 

Given Function

  • Declare and initialize 64Bit integer ‘ans’ to 0.
  • Declare integer array ‘subset’
  • subsets(arr, subset, ans)
  • Return ans
Time Complexity

O(2^N * N) where N is the size of Arr.

 

We are going to generate all the 2^N subsets of given Arr and then check for validity for each subset which takes O(N) time. So total time will be equal to O(2^N) * O(N) = O(2^N * N).

Space Complexity

O(N) where N is the size of Arr.

 

We only need extra space for the subset array and recursion stack. Both of these are at most the size of O(N). So total space required will be O(N).

Code Solution
(100% EXP penalty)
Unit Power Subsets
Full screen
Console