Formatted question description: https://leetcode.ca/all/1735.html
1735. Count Ways to Make Array With Product
Level
Hard
Description
You are given a 2D integer array, queries
. For each queries[i]
, where queries[i] = [n_i, k_i]
, find the number of different ways you can place positive integers into an array of size ni such that the product of the integers is k_i
. As the number of ways may be too large, the answer to the i-th
query is the number of ways modulo 10^9 + 7
.
Return an integer array answer
where answer.length == queries.length
, and answer[i]
is the answer to the i-th
query.
Example 1:
Input: queries = [2,6,5,1,73,660]
Output: [4,1,50734910]
Explanation: Each query is independent.
Example 2:
Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: [1,2,3,10,5]
Constraints:
1 <= queries.length <= 10^4
1 <= n_i, k_i <= 10^4
Solution
First, get all combination numbers for all possible values of n
and k
. Next, for each query (n, k)
, do prime factorization for k
and calculate the number of ways using the combination numbers and the prime factorization results of k
.
class Solution {
int[] primes = new int[14];
int[] exponents = new int[14];
int index = 0;
long[][] combinations = new long[11000][20];
static final int MODULO = 1000000007;
public int[] waysToFillArray(int[][] queries) {
for (int i = 0; i < 10500; i++) {
combinations[i][0] = 1;
if (i < 15)
combinations[i][i] = 1;
int end = Math.min(i, 15);
for (int j = 1; j < end; j++)
combinations[i][j] = (combinations[i - 1][j - 1] + combinations[i - 1][j]) % MODULO;
}
int queriesCount = queries.length;
int[] ways = new int[queriesCount];
for (int i = 0; i < queriesCount; i++) {
int n = queries[i][0], k = queries[i][1];
long way = 1;
fact(k);
for (int j = 1; j <= index; j++)
way = way * combinations[n + exponents[j] - 1][exponents[j]] % MODULO;
ways[i] = (int) way;
}
return ways;
}
public void fact(int n) {
index = 0;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
index++;
primes[index] = i;
exponents[index] = 0;
while (n % i == 0) {
exponents[index]++;
n /= i;
}
}
}
if (n != 1) {
index++;
primes[index] = n;
exponents[index] = 1;
}
}
}