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.
| 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 |
| 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