Watch 4 video solutions for Count Ways to Make Array With Product, a hard level problem involving Array, Math, Dynamic Programming. This walkthrough by Happy Coding has 1,375 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D integer array, queries. For each queries[i], where queries[i] = [ni, ki], 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 ki. As the number of ways may be too large, the answer to the ith query is the number of ways modulo 109 + 7.
Return an integer array answer where answer.length == queries.length, and answer[i] is the answer to the ith query.
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 109 + 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 <= 104 1 <= ni, ki <= 104Problem Overview: Each query gives n and k. You must count how many arrays of length n consisting of positive integers have a product equal to k. The answer for each query is returned modulo 1e9 + 7.
Approach 1: Prime Factorization + Combinatorics (O(q * sqrt(k)) time, O(N) space)
The key observation: if the product of an array equals k, then the prime factorization of all elements combined must equal the prime factorization of k. Factorize k into primes, e.g. k = p1^e1 * p2^e2 .... For each prime factor, you distribute its exponent across n array positions. This becomes a classic stars and bars problem: the number of ways to distribute e identical items across n slots is C(e + n - 1, n - 1). Multiply this value for every prime factor of k. Precompute factorials and modular inverses to evaluate combinations quickly. Factorization costs O(sqrt(k)) per query and each combination lookup is O(1). This approach relies heavily on number theory and combinatorics.
Approach 2: Dynamic Programming Distribution (O(q * e * n) time, O(n * e) space)
Instead of using the direct combinatorics formula, you can compute the distribution counts using dynamic programming. For a prime exponent e, define dp[i][j] as the number of ways to distribute j factors across the first i positions. Transition: either assign zero factors to the current position or add more by extending previous states. This effectively builds the same values as C(j + i - 1, i - 1). Run this DP for each prime exponent extracted from k, then multiply the results across primes. While conceptually clear, the DP is slower than the direct combinatorics formula and uses more memory. It demonstrates how the counting emerges from incremental state transitions using dynamic programming.
Recommended for interviews: The prime factorization + combinatorics approach is the expected solution. Interviewers want to see that you reduce the product constraint to exponent distribution and recognize the stars and bars formula. A brute-force enumeration of arrays is infeasible because the search space grows exponentially. Showing the mathematical reduction demonstrates strong problem-solving skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Prime Factorization + Combinatorics | O(q * sqrt(k)) | O(N) | Best general solution for multiple queries; fastest when factorials are precomputed |
| Dynamic Programming Distribution | O(q * e * n) | O(n * e) | Useful for understanding exponent distribution logic or when deriving the combinatorics formula |