Scale Engineer

Count Ways to Make Array With Product

Hard
#1589Time: `O(P + Q * sqrt(max_k))`, where `P` is the precomputation time for factorials, `O(max_n + max_e)`. With `Q <= 10^4` and `max_k <= 10^4`, the total time is dominated by processing queries, resulting in `O(10^4 * sqrt(10^4)) = O(10^6)` operations, which is acceptable.Space: `O(max_n + max_e)` to store the precomputed factorial and inverse factorial arrays. Given the constraints, this is `O(10^4)`.
Patterns
MathDynamic ProgrammingCombinatoricsNumber Theory
Data structures
Array

Prompt

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 <= 104

Approaches

2 approaches with complexity analysis and trade-offs.

This approach tackles the problem by first understanding its mathematical structure. The problem of finding the number of arrays of size n with a product k can be broken down by considering the prime factorization of k. If k = p_1^{e_1} * p_2^{e_2} * ... * p_m^{e_m}, then for each prime factor p_i, we need to distribute its total power e_i among the n elements of the array. This is a classic combinatorial problem known as "stars and bars". The number of ways to distribute e identical items into n distinct bins is C(n + e - 1, e). The total number of ways is the product of these values for each prime factor. This approach calculates this for each query individually.

Algorithm

    1. Precompute factorials and their modular inverses up to a maximum possible value of n + e - 1. Given n <= 10^4 and k <= 10^4, the maximum exponent e is for 2^e <= 10^4, which is e=13. So we need factorials up to 10000 + 13 = 10013.
    1. Create a result array answer of the same size as queries.
    1. Iterate through each query [n, k] in queries.
    1. For each query, initialize a variable ways = 1.
    1. Find the prime factorization of k. Iterate a divisor d from 2 up to sqrt(k).
    1. If d divides k, count its exponent e. Then, calculate C(n + e - 1, e) using the precomputed tables and multiply it into ways. Update k by dividing out d^e.
    1. If k is still greater than 1 after the loop, it is a prime factor itself. Its exponent is 1. Calculate C(n + 1 - 1, 1) = C(n, 1) = n and multiply it into ways.
    1. Store the final ways in the answer array.
    1. Return answer.

Walkthrough

The core of the solution is to transform the multiplicative problem into a set of independent additive problems. Let the array be A = [a_1, a_2, ..., a_n] and Product(A) = k. Let the prime factorization of k be p_1^{e_1} * p_2^{e_2} * ... * p_m^{e_m}. Each element a_i can be written as a_i = p_1^{e_{i1}} * p_2^{e_{i2}} * ... * p_m^{e_{im}}. The condition Product(A) = k implies that for each prime p_j, the sum of its exponents across all a_i must equal e_j. That is, sum_{i=1 to n} e_{ij} = e_j. This is a "stars and bars" problem. The number of non-negative integer solutions to this equation is C(n + e_j - 1, e_j). Since the distribution of exponents for each prime is independent, the total number of ways is the product: ways = Product_{j=1 to m} C(n + e_j - 1, e_j). For each query [n, k], we perform the following steps:

  1. Find the prime factors of k and their exponents using trial division (iterating from 2 up to sqrt(k)).
  2. For each exponent e, calculate C(n + e - 1, e) modulo 10^9 + 7.
  3. Multiply all these results together to get the final answer for the query. To compute C(N, R) % MOD efficiently, we precompute factorials and their modular multiplicative inverses. This is done once before processing any queries.
class Solution {    private static final int MOD = 1_000_000_007;    private static final int MAX_N_PLUS_E = 10000 + 14; // max_n=10000, max_e for k=10000 is for 2^13=8192, so e=13.    private static long[] fact = new long[MAX_N_PLUS_E];    private static long[] invFact = new long[MAX_N_PLUS_E];     static {        fact[0] = 1;        invFact[0] = 1;        for (int i = 1; i < MAX_N_PLUS_E; i++) {            fact[i] = (fact[i - 1] * i) % MOD;            invFact[i] = power(fact[i], MOD - 2);        }    }     private static long power(long base, long exp) {        long res = 1;        base %= MOD;        while (exp > 0) {            if (exp % 2 == 1) res = (res * base) % MOD;            base = (base * base) % MOD;            exp /= 2;        }        return res;    }     private long nCr_mod_p(int n, int r) {        if (r < 0 || r > n) return 0;        if (r > n / 2) r = n - r;        return (((fact[n] * invFact[r]) % MOD) * invFact[n - r]) % MOD;    }     public int[] waysToFillArray(int[][] queries) {        int[] ans = new int[queries.length];        for (int i = 0; i < queries.length; i++) {            int n = queries[i][0];            int k = queries[i][1];                        long currentWays = 1;                        for (int p = 2; p * p <= k; p++) {                if (k % p == 0) {                    int count = 0;                    while (k % p == 0) {                        count++;                        k /= p;                    }                    currentWays = (currentWays * nCr_mod_p(n + count - 1, count)) % MOD;                }            }            if (k > 1) {                int count = 1;                currentWays = (currentWays * nCr_mod_p(n + count - 1, count)) % MOD;            }            ans[i] = (int) currentWays;        }        return ans;    }}

Complexity

Time

`O(P + Q * sqrt(max_k))`, where `P` is the precomputation time for factorials, `O(max_n + max_e)`. With `Q <= 10^4` and `max_k <= 10^4`, the total time is dominated by processing queries, resulting in `O(10^4 * sqrt(10^4)) = O(10^6)` operations, which is acceptable.

Space

`O(max_n + max_e)` to store the precomputed factorial and inverse factorial arrays. Given the constraints, this is `O(10^4)`.

Trade-offs

Pros

  • Conceptually straightforward, directly translating the mathematical formula.

  • Implementation is relatively simple.

Cons

  • The prime factorization step O(sqrt(k)) is performed for every query, which can be inefficient if the number of queries is large.

Solutions

class Solution {private  static final int N = 10020;private  static final int MOD = (int)1 e9 + 7;private  static final long[] F = new long[N];private  static final long[] G = new long[N];private  static final List<Integer>[] P = new List[N];  static {    F[0] = 1;    G[0] = 1;    Arrays.setAll(P, k->new ArrayList<>());    for (int i = 1; i < N; ++i) {      F[i] = F[i - 1] * i % MOD;      G[i] = qmi(F[i], MOD - 2, MOD);      int x = i;      for (int j = 2; j <= x / j; ++j) {        if (x % j == 0) {          int cnt = 0;          while (x % j == 0) {            ++cnt;            x /= j;          }          P[i].add(cnt);        }      }      if (x > 1) {        P[i].add(1);      }    }  }public  static long qmi(long a, long k, long p) {    long res = 1;    while (k != 0) {      if ((k & 1) == 1) {        res = res * a % p;      }      k >>= 1;      a = a * a % p;    }    return res;  }public  static long comb(int n, int k) {    return (F[n] * G[k] % MOD) * G[n - k] % MOD;  }public  int[] waysToFillArray(int[][] queries) {    int m = queries.length;    int[] ans = new int[m];    for (int i = 0; i < m; ++i) {      int n = queries[i][0], k = queries[i][1];      long t = 1;      for (int x : P[k]) {        t = t * comb(x + n - 1, n - 1) % MOD;      }      ans[i] = (int)t;    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem