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 <= 104The 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.
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.
C#
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 |
Product of Array Except Self - Leetcode 238 - Python • NeetCode • 747,485 views views
Watch 9 more video solutions →Practice Count Ways to Make Array With Product with our built-in code editor and test cases.
Practice on FleetCode