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.
The main idea is to perform prime factorization of ki for each query and then calculate the number of ways to distribute the factors among the array elements. After prime factorizing ki as p1^a1 * p2^a2 * ... * pk^ak, the problem reduces to distributing each ai weight into ni slots which can be solved using combinations with repetitions formula combined with modular arithmetic to handle large numbers.
This Python function uses prime factorization to convert the problem of calculating ways to fill an array to a combinatorial one. First, prime_factors extracts the prime factors and their counts from ki. We calculate the binomial coefficient using binomial_coefficient to find ways to distribute each factor's occurrences. The final result for each query is calculated modulo 109 + 7.
Python
JavaScript
Time Complexity: O(√k + n log MOD) for each query, where k is the integer to factorize and n is determined by the queries.
Space Complexity: O(1), excluding input and output storage.
This alternative approach uses a dynamic programming array to iteratively build up the solution for each query. By recalculating results based on sub-problems, we ensure efficiency. This approach is more intuitive but involves caching previously computed results to avoid recomputation and thus save time.
This Java implementation uses dynamic programming to explore sub-problems through binomial coefficients. It calculates results for each step iteratively, ensuring that each computed solution aids in building towards the final answer. The use of a hashmap for factorization and caching improves performance by reducing recalculations.
Time Complexity: O(√k + n log MOD) for each query
Space Complexity: O(1), excluding input and output storage.
We can perform prime factorization on k, i.e., k = p_1^{x_1} times p_2^{x_2} times cdots times p_m^{x_m}, where p_i is a prime number, and x_i is the exponent of p_i. The problem is equivalent to: placing x_1 p_1s, x_2 p_2s, cdots, x_m p_ms into n positions respectively, where a single position can be empty. The question is how many schemes are there.
According to combinatorial mathematics, there are two cases when we put x balls into n boxes:
If the box cannot be empty, the number of schemes is C_{x-1}^{n-1}. This is using the partition method, i.e., there are a total of x balls, and we insert n-1 partitions at x-1 positions, thereby dividing the x balls into n groups.
If the box can be empty, we can add n virtual balls, and then use the partition method, i.e., there are a total of x+n balls, and we insert n-1 partitions at x+n-1 positions, thereby dividing the actual x balls into n groups and allowing the box to be empty. Therefore, the number of schemes is C_{x+n-1}^{n-1}.
Therefore, for each query queries[i], we can first perform prime factorization on k to get the exponents x_1, x_2, cdots, x_m, then calculate C_{x_1+n-1}^{n-1}, C_{x_2+n-1}^{n-1}, cdots, C_{x_m+n-1}^{n-1}, and finally multiply all the scheme numbers.
So, the problem is transformed into how to quickly calculate C_m^n. According to the formula C_m^n = \frac{m!}{n!(m-n)!}, we can pre-process m!, and then use the inverse element to quickly calculate C_m^n.
The time complexity is O(K times log log K + N + m times log K), and the space complexity is O(N).
| Approach | Complexity |
|---|---|
| Prime Factorization and Combinatorics | Time Complexity: O(√k + n log MOD) for each query, where k is the integer to factorize and n is determined by the queries. |
| Dynamic Programming Approach | Time Complexity: O(√k + n log MOD) for each query |
| Prime Factorization + Combinatorial Mathematics | — |
| 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 |
LeetCode 1735. Count Ways to Make Array With Product • Happy Coding • 1,375 views views
Watch 3 more video solutions →Practice Count Ways to Make Array With Product with our built-in code editor and test cases.
Practice on FleetCode