Use prime factorization of k to break the problem into independent distributions of primes. For each prime, compute how many ways to assign its powers across n positions using combinatorial counting. Combine results modulo 10^9 + 7 for each query efficiently with dynamic programming.
Problem Statement
Given a list of queries, each query consists of two integers n and k. For each query, compute the number of arrays of length n filled with positive integers such that the product of all elements equals k. Return the results modulo 10^9 + 7.
Each query is independent. For example, if n = 2 and k = 6, valid arrays include [1,6], [2,3], [3,2], and [6,1], totaling 4 ways. Process all queries and return an array of answers corresponding to the input queries order.
Examples
Example 1
Input: queries = [[2,6],[5,1],[73,660]]
Output: [4,1,50734910]
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]
Example details omitted.
Constraints
- 1 <= queries.length <= 104
- 1 <= ni, ki <= 104
Solution Approach
Prime Factorization
Decompose k into its prime factors. Each prime and its exponent can be distributed among n positions independently, transforming the product problem into multiple combination problems for each prime.
Combinatorial DP
For each prime factor with exponent e, compute the number of ways to assign e identical items to n positions using the formula C(e+n-1, n-1). Use precomputed factorials and modular inverses to handle large numbers efficiently.
Aggregate Results
Multiply the counts of distributions for all prime factors to get the total number of valid arrays for each query. Apply modulo 10^9 + 7 at each multiplication step to avoid overflow.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity depends on prime factorization of k and the calculation of combinations for each prime exponent across n positions. Space complexity is mainly for factorial tables and storing intermediate results for each query.
What Interviewers Usually Probe
- Expect candidates to recognize prime factorization reduces multiplicative constraints to additive distributions.
- Look for correct handling of large numbers and modulo arithmetic in combinatorial calculations.
- Strong solutions efficiently precompute factorials to avoid recomputation for multiple queries.
Common Pitfalls or Variants
Common pitfalls
- Failing to account for modulo arithmetic during combination calculations, leading to integer overflow.
- Miscounting distributions of prime powers when exponents are large compared to n.
- Not separating queries properly, causing mixing of results across independent queries.
Follow-up variants
- Counting arrays with a sum constraint instead of a product using similar combinatorial DP techniques.
- Handling arrays with restricted value ranges, requiring adjusted prime distributions.
- Extending to multi-dimensional arrays where the product constraint applies along different axes.
How GhostInterview Helps
- GhostInterview automatically identifies prime factorization and sets up distribution DP for each query.
- It ensures modular arithmetic and factorial precomputation are applied correctly to prevent overflow errors.
- Provides step-by-step reasoning to combine individual prime distributions, streamlining the calculation for multiple queries.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
How do I start solving Count Ways to Make Array With Product efficiently?
Begin by prime factorizing k for each query. Then, distribute prime exponents across n positions using combinatorial counting, applying modulo 10^9 + 7.
Why is combinatorial DP used in this problem?
Combinatorial DP counts the ways to distribute prime exponents across positions, which is equivalent to placing identical items into distinct bins efficiently.
How should large numbers be handled in calculations?
Use modular arithmetic at every multiplication and combination step. Precompute factorials and modular inverses for fast combination evaluation.
Can this approach handle multiple queries efficiently?
Yes, by precomputing factorials and inverses, each query’s calculation reduces to processing prime distributions without recomputing combinatorial values.
Is state transition dynamic programming always necessary here?
Yes, DP effectively manages distributions of prime powers for each position, ensuring correct counts while handling constraints and modulo operations.
Need direct help with Count Ways to Make Array With Product instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Count Ways to Make Array With Product from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Maximize the score after n operations by selecting pairs from the array and using their GCD with dynamic programming or backtracking techniques.
Open problem page#1643 Kth Smallest InstructionsFind the kth smallest lexicographic instruction sequence for reaching a destination in a grid using state transition dynamic programming.
Open problem page#1569 Number of Ways to Reorder Array to Get Same BSTDetermine the number of ways to reorder an array to get the same binary search tree (BST) from its insertion order.
Open problem page