Last Updated: 10 Feb, 2021
Count Sequences Of Positive Integers Having Product X
Hard
Asked in companies
You are given an array 'NUM' consisting of N positive Integers. Your task is to find the total number of possible sequences of positive integers (greater than 1) whose product is 'X'.
The value of 'X' is calculated as the product of the N terms, where the ith term is generated by raising the ith prime number to the power of an ith element in the given array.
In mathematical terms, we can write X as:
X = 2 ^ NUM[1] * 3 ^ NUM[2] * 5 ^ NUM[3] * 7 ^ NUM[4] * 11 ^ NUM[5] * … up to Nth term
Note :
1. Sum of all the elements in the array 'NUM' will always be less than or equal to 400.
2. As the total number of such sequences can be very large, print the answer modulo 1000000007.
Input Format:
The first line of input contains a single integer T, representing the number of test cases
Then the T test cases follow.
The first line of each test case contains a number N denoting the size of the array 'NUM'.
The second line contains N space-separated integers, the elements of 'NUM'.
Output format:
For each test case print in a new line, an integer representing the total number of possible sequences of positive integers (greater than 1) whose product is X.
Note
You don’t have to print anything, it has already been taken care of. Just implement the given function.
Constraints
1<= T <=10
2 <= N <= 500
1 <= NUM[i] < 100
Time Limit : 1 sec
Approaches
The idea is to make use of a combinatorics approach to find the contribution made by each element of the array in a total number of sequences.
- The maximum number of positive integers in a sequence can be equal to the total sum of array elements, as explained below.
- If given array is {1,1} then :
- {1,1} = 2^1 * 3^1 = 6 so we can have a maximum 2 prime whose product is 6.
- Let's say the total sum of array elements is S.
- We will make an array of integers say ANS[S+1], initialize to zero, which will store the contribution made by ith array element to a total number of sequences.
- We will also make a 2-D array of integers say BCOFF[500][500], BCOFF will store permutations of binomial coefficients.
- Then use dynamic programming to fill the slots in the possible sequences starting from index 1 to S.
- For each j-th prime number having power as ARR[j], divide all the ARR[j] primes into each of the i slots.
- Use the Combinatorics Approach to divide ARR[j] elements into i slots.
- Store the value in array ARR such that ARR[i] is updated as follows:
- ARR[i]= ARR[i] * (ARR[j]+i-1)C(i-1).
- Here we are using nCr, which is the method of selection of ‘r’ objects from a set of ‘n’ objects where the order of selection does not matter.
- We can find this value from BCOFF array, or we can say : ARR[i]= ARR[i] * BCOFF[ ARR[j]+i-1 ][ i-1].
- However, ANS will also contain the sequences with one or more than 1 slot empty, hence subtract the exact contribution for all slots where the number of slots filled is less than i.
- For each of the slots from j = 1 to i-1, select j slots from i and subtract its contribution and update ARR[i] as ARR[i] = ARR[i]-BCOFF[i][j].
- Now the sum of ANS elements will be our answer.
Let’s understand with an example:
- Let’s take an example {1,0,1}:
- Then the value of X = 2^1*3^0*5^1 = 10 .
- Now as the sum of the array is 2 (S=2), there can be a maximum of 2 numbers in sequences whose product is 10.
- ANS[3]= {0,0,0}.
- We will run a loop for i = 1 to i = 3 and inside this loop, we will run a loop for j = 0 to j < 2 and :
- ANS[i]=1 and then ANS[i] will be multiplied by (ARR[j]+i-1)C(i-1), here we are dividing ARR[j] + i - 1 into i - 1 slots.
- But ARR[i] will also contain the sequences with one or more than 1 slot empty, so to get the exact contribution we will do:
- ANS[i] = ANS[i]- ANS[i]*(iCj).
- After completion of the above step, ANS will be [0,1,2] which will add up to 3.
- So our answer will be 3.
Similar problems