#1735

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Count Ways to Make Array With Product

Determine the number of arrays of size n where the product equals k using prime factorization and combinatorial DP techniques.

array math dynamic programming combinatorics number theory

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.

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.

terminal

Solution

Solution 1: Prime Factorization + Combinatorial Mathematics

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_1$s, $x_2$ $p_2$s, $\cdots$, $x_m$ $p_m$s into $n$ positions respectively, where a single position can be empty. The question is how many schemes are there.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

N = 10020
MOD = 10**9 + 7
f = [1] * N
g = [1] * N
p = defaultdict(list)
for i in range(1, N):
    f[i] = f[i - 1] * i % MOD
    g[i] = pow(f[i], MOD - 2, MOD)
    x = i
    j = 2
    while j <= x // j:
        if x % j == 0:
            cnt = 0
            while x % j == 0:
                cnt += 1
                x //= j
            p[i].append(cnt)
        j += 1
    if x > 1:
        p[i].append(1)


def comb(n, k):
    return f[n] * g[k] * g[n - k] % MOD


class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
        ans = []
        for n, k in queries:
            t = 1
            for x in p[k]:
                t = t * comb(x + n - 1, n - 1) % MOD
            ans.append(t)
        return ans

Continue Practicing

#1799 maximize score after n operations #1643 kth smallest instructions #1569 number of ways to reorder array to get same bst