Count Ways To Make Array With Product

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
3 upvotes
Asked in company
Nagarro Software

Problem statement

There are two friends Ranbir and Alia. Ranbir gave a question to Alia that you are given ‘Q’ queries in the form [N, P].

For each query, Alia has to count how many arrays consisting of positive integers of size ‘N’ she could build such that the product of all the array elements is equal to ‘P’.

Since the answer could be large, return the answer to each query modulo 10^9 + 7.

Detailed explanation ( Input/output format, Notes, Images )
Input format : 
The first line of input contains an integer ‘T’, denoting the number of test cases. 

The first line of each test contains an integer ‘Q’ denoting the total number of Queries.

Then each of the next ‘Q’ lines contains two space-separated integers ‘N’ and ‘P’ denoting the size of the array to be formed and the product it should have after the array is formed respectively.
Output format : 
For each test case, print the count of arrays formed for each query in a single line.

Output for each test case is printed on a separate line.
Note : 
You do not need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= Q <= 10^4
1 <= N , P <= 10^4

Time Limit: 1 sec
Sample Input 1 :
2
2
2 6
1 1
1
5 1
Sample Output 1 :
4 1
1
Explanation For Sample Input 1 :
For the first test case, consider each query independently

For the first query where we have to build an array of size 2 and the product of array, elements should be equal to 6. So all the possible arrays are: {1, 6}, {6, 1}, {2, 3} and {3, 2}. Therefore, the answer will be 4 for the given query.

For the second query where we have to build an array of size 1 and the product of the array, elements should be equal to 1. So the only possible array is {1}. Therefore, the answer will be 1 for the given query.

For the second test case, consider each query independently

For the first query where we have to build an array of size 5 and the product of array elements should be equal to 1. So the only possible array is {1, 1, 1, 1, 1}. Therefore, the answer will be 1 for the given query.
Sample Input 2 :
2
2
7 20
2 2
2
3 6
3 4
Sample Output 2 :
196 2
9 6
Hint

Make a dynamic programming solution where each DP[i][j] state will denote ways to fill i places in an array whose product is j. 

Approaches (2)
Dynamic Programming Approach
  • The idea behind this approach is that DP[N][P] will hold our result for any query.
  • So we will build a solution step by step in a bottom-up manner.
  • We will create a DP table in which each DP[i][j] state will represent the ways to make an array of size i with a product of j.
  • The recurrence relation that we will use will be:
DP[i][j] = DP[i][j] + sum of (DP[i-1][j / divisors(j)]).
  • The number of elements reduces by one because we have added the divisor j in our current array so to add another divisor i.e j / divisor we have reduced the size of the array by 1.

 

Algorithm:

 

  • Create an array ans to store the answer to each query.
  • Now iterate over all queries and for each query perform the following steps:
    • Create a DP table of size (N+1) * (P+1) all initialized with 0.
    • Now fill the first row of the DP table i.e DP[1][j] starting from j=1 to j = P with 1 because to fill an array of size 1 there could be only one way.
    • Similarly, fill the first column of the DP table i.e DP[i][1] starting from i = 1 to i = N with 1 because to build an array with product 1 there could be only one way.
    • Now for each i from 2 to N take the value of j from 2 to P and for each value of j perform the following steps:
      • For each divisor of j update DP[i][j] as DP[i][j] = DP[i][j]  + DP[i-1][j/divisor(j)].
      • Then update DP[i][j] as DP[i][j] % 1000000007.
    • Now finally add DP[N][P] in our ans.
  • Finally, return the array ans.
Time Complexity

O(Q * N * P * Sqrt(P)), where ‘Q’ is the total number of queries, ‘N’ is the size of the array to build and ‘P’ is the product that the array should have.

 

Since we are iterating over all queries which take O(Q) time and for each query we are constructing a DP table of size (N+1) * (P+1) and for each value of P, we are calculating its divisors which in total take O(N * P * Sqrt(P)) time. 

 

So overall time complexity will be O(Q * N * P * Sqrt(P)).

Space Complexity

O(N * P), where  ‘N’ is the size of the array to build and ‘P’ is the product that the array should have.

 

Since we are constructing a DP table of size (N+1) * (P+1) which takes O(N * P) space. So overall space complexity will be O(N * P).

Code Solution
(100% EXP penalty)
Count Ways To Make Array With Product
Full screen
Console