This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1735 (Hard): Count Ways to Make Array With Product
Description:
You are given a 2D integer array, queries. For each queries[i], where queries[i] = [n, k], find the number of different ways you can place positive integers into an array of size n such that the product of the integers is k. As the number of ways may be too large, the answer to the ith 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 ith query.
Examples:
| Example 1: | |
|---|---|
| Input: | queries = [[2,6],[5,1],[73,660]] |
| Output: | [4,1,50734910] |
| Explanation: | Each query is independent. [2,6]: There are 4 ways to fill an array of size 2 that multiply to 6: [1,6], [2,3], [3,2], [6,1]. [5,1]: There is 1 way to fill an array of size 5 that multiply to 1: [1,1,1,1,1]. [73,660]: There are 1050734917 ways to fill an array of size 73 that multiply to 660. 1050734917 modulo 10^9 + 7 = 50734910. |
| 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, k <= 10^4
Idea:
The easier part of this solution is to recognize that each number can be broken up at most into its prime factors, so our first step will be to identify these prime factors. Once we do that, the more difficult realization is that we have a combinatorics problem that can best be described as a "series of combinations with repetition".
Take, for example, queries [3,4] and [3,6]. We can easily see that the prime factors of 4 are {2,2} and of 6 are {2,3}. The possible solutions here differ, however, because the first query has a repeating 2:
permutations for query = [3,4]: [4,1,1], [1,4,1], [1,1,4],
[2,2,1], [2,1,2], [1,2,2]
permutations for query = [3,6]: [6,1,1], [1,6,1], [1,1,6],
[3,2,1], [3,1,2], [2,3,1],
[2,1,3], [1,3,2], [1,2,3]
So let's break this down for a second. Query [3,6] is simple because none of the choices of where to put an item impact another. To think about it in simple terms, you have a sequence of decisions of where to put each item, and at each step, you can put each item into any position. So you have 3 options in which to place the first item and 3 options in which to place the second item, leading to 3 * 3 = 9 possible permutations. It's clear that in non-repeating prime scenarios of r primes into n positions, the answer will be n^r.
Despite the fact that we just showed that the formula for a non-repeating combinations was n^r, that equation is actually a simplification of what is actually happening: a series (of length r) of n choose 1 equations. The equation "n choose r" is a formula to represent the permutations for picking in which of n positions to place r items.
n choose r: n choose 1:
n! n! (n - 1)! * n n
---------- ---------- = -------------- = --- = n
(n - r)! (n - 1)! (n - 1)! 1
So we can see that n^r is just the simplification of a much larger formula. In our query [3,6] example, that would stretch out into:
series of two 3 choose 1 combinations:
3! 3! 3 3
---------- * ---------- = --- * --- = 3 * 3 = 9
(3 - 1)! (3 - 1)! 1 1
But how does the repeating 2 in query [3,4] impact this? In this case, instead of two choices of non-repeating items being placed into three positions, we have one set of two repeating items being placed into three positions. The formula for this is described as r + n - 1 choose r:
r + n - 1 choose r: 2 + 3 - 1 choose 2:
(r + n - 1)! (2 + 3 - 1)! 4! 24
--------------- --------------- = --------- = ----- = 6
r! * (n - 1)! 2! * (3 - 1)! 2! * 2! 4
And if this formula works for any amount of repeated numbers, it should also work for single numbers (r = 1), too:
r + n - 1 choose r: 1 + n - 1 choose 1 = n choose 1
(r + n - 1)! (1 + n - 1)! n!
--------------- --------------- = ----------
r! * (n - 1)! 1! * (n - 1)! (n - 1)!
Then what about a more complicated scenario, such as query [3,540]? In that situation, we have prime factors of {2,2,3,3,3,5}. In this case, just like before, we can think of this as a series of equations, using the above formula for each distinct prime number, where r is the frequency of that prime number, and n is the array size:
query [3,540] =
two 2s three 3s one 5
r = 2, n = 3 * r = 3, n = 3 * r = 1, n = 3
2+3-1 choose 2 3+3-1 choose 3 1+3-1 choose 1
(2 + 3 - 1)! (3 + 3 - 1)! (1 + 3 - 1)!
--------------- * --------------- * --------------- = 6 * 10 * 3 = 180
2! * (3 - 1)! 3! * (3 - 1)! 1! * (3 - 1)!
Perfect. With this, we can build out an iteration loop to complete these equations for each query, once we've figured out the prime factors and their frequencies. In fact, we don't really care about the primes themselves, only their frequencies. Also, remember that the bulk of these factorials will cancel out, so you don't need to waste time iterating from 1 to n, usually. As n will almost always be larger than r, you can easily cancel out the (n - 1)! on the bottom with all but the last r numbers of the (r + n - 1)!:
r+n-1 choose r:
(r + n - 1)! (n-1)!*(n+0)*(n+1)*...*(n+r-1) (n+0)*(n+1)*...*(n+r-1)
--------------- = -------------------------------- = -------------------------
r! * (n - 1)! r! * (n - 1)! r!
(r + n - 1)! n + r - i
so: --------------- = loop i from 1 to r, multiply together: -----------
r! * (n - 1)! i
Then we just need to remember to mod 1e9+7 each prime result before multiplying all the results together.
Javascript Code:
const waysToFillArray = Q => Q.map(solve)
const solve = query => {
let [n, k] = query, count = 0, ans = 1,
freqs = primeFactorFreqs(k)
for (let i = 0; i < freqs.length; i++) {
let freq = freqs[i], res = 1n
for (let r = 1; r <= freq; r++)
res = res * BigInt(r + n - 1) / BigInt(r)
ans = Number(BigInt(ans) * res % 1000000007n)
}
return ans
}
const primeFactorFreqs = num => {
let pf = [], count = 0
for (let i = 2; i <= Math.sqrt(num); i++) {
while (num % i === 0) count++, num /= i
if (count) pf.push(count), count = 0
}
if (num !== 1) pf.push(1)
return pf
};
Top comments (0)