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 <= 104To solve #1735 Count Ways to Make Array With Product, the key idea is to think in terms of prime factorization. For each query with array length n and product k, first break k into its prime factors. Each prime factor contributes some exponent, and the challenge becomes distributing these exponents across n array elements.
This distribution can be modeled using the stars and bars combinatorial technique. If a prime factor appears e times in the factorization, the number of ways to distribute it among n positions is C(n + e - 1, e). Multiply the results for all prime factors to get the total number of valid arrays.
To make the solution efficient for many queries, precompute combinations using factorials and modular inverses under 10^9 + 7. Each query then performs prime factorization and multiplies the corresponding combinations. This approach avoids brute-force enumeration and leverages number theory and combinatorics for efficiency.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prime Factorization + Combinatorics (Stars and Bars) | O(Q * sqrt(k)) for factorization with O(1) combination lookup | O(N) for factorial and inverse precomputation |
| Precomputed Combinations with Modular Arithmetic | O(N) preprocessing + O(Q * log k) typical factorization | O(N) for factorial tables |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Prime-factorize ki and count how many ways you can distribute the primes among the ni positions.
After prime factorizing ki, suppose there are x amount of prime factor. There are (x + n - 1) choose (n - 1) ways to distribute the x prime factors into n positions, allowing repetitions.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Stars and bars is used because the task becomes distributing identical prime factors across multiple array indices. If a prime factor appears e times, stars and bars counts the ways to place those e identical items into n buckets.
Problems involving prime factorization and combinatorics appear in advanced interview rounds at top companies. While this exact question may not always appear, similar patterns combining number theory and combinatorics are common in FAANG-level interviews.
The problem mainly relies on combinatorics and number theory. Prime factorization identifies exponent counts, and combinations (nCr) help compute how those exponents can be distributed across array positions.
The optimal approach uses prime factorization combined with the stars and bars combinatorial technique. After factorizing the product, distribute each prime exponent across the array length using combinations like C(n + e - 1, e). Precomputing factorials and modular inverses allows fast computation for multiple queries.