LeetCode 1735: Count Ways to Make Array With Product
Problem Description
Explanation
To solve this problem, we can use dynamic programming. We will iterate through all possible factors of the given product k and for each factor that divides k, we will calculate the number of ways to form an array of size n with that factor as the maximum element. We will store these counts in a 2D array dp. The final answer for each query will be the sum of all possible ways to form the product k by considering all factors.
- Initialize a 2D array
dpof sizen+1xk+1wheredp[i][j]represents the number of ways to form an array of sizeiwith productj. - For each query
[n, k]:- Iterate through all factors
fofk. - For each factor, calculate the number of ways to form an array of size
nwithfas the maximum element by considering all possible smaller factors. - Update
dp[n][k]accordingly.
- Iterate through all factors
- Return the result for each query modulo
10^9 + 7.
Time Complexity: O(n * k * sqrt(k)) where n is the number of queries and k is the maximum product value in the queries. The inner loop runs for each factor of k.
Space Complexity: O(n * k) for the 2D array dp.
Solutions
class Solution {
public int[] waysToFillArray(int[][] queries) {
int mod = 1000000007;
int maxN = 10000;
int[][] dp = new int[maxN + 1][maxN + 1];
dp[0][1] = 1;
for (int i = 1; i <= maxN; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = (dp[i - 1][j - 1] + dp[i][j - 1]) % mod;
}
}
int[] result = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int n = queries[i][0];
int k = queries[i][1];
int ways = 1;
for (int factor = 2; factor * factor <= k; factor++) {
if (k % factor == 0) {
int count = 0;
while (k % factor == 0) {
count++;
k /= factor;
}
ways = (int) ((long) ways * dp[n + count - 1][count] % mod);
}
}
if (k > 1) {
ways = (int) ((long) ways * dp[n][1] % mod);
}
result[i] = ways;
}
return result;
}
}Loading editor...