Count Ways to Make Array With Product — Hard Problem & Solution

Each query queries[i] = [n, k] asks: how many arrays of n positive integers have a product of exactly k? Return the answers in order, each modulo 10⁹ + 7.

Difficulty: Hard
Topics: Arrays, Math, Dynamic Programming, Number Theory, Combinatorics
Asked at: Amazon, Google, Microsoft
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each query queries[i] = [n, k] asks: how many arrays of n positive integers have a product of exactly k?

Return the answers in order, each modulo 10⁹ + 7.

Example 1

Input: queries = [[2,6],[5,1],[73,660]]
Output: [4,1,50734910]
Explanation: For `[2,6]`: `[1,6]`, `[2,3]`, `[3,2]`, `[6,1]`.

Example 2

Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: [1,2,3,10,5]

Example 3

Input: queries = [[3,8]]
Output: [10]
Explanation: 8 = 2³, and three factors of 2 spread over three slots is `C(5,3)`.

Constraints

1 <= queries.length <= 10^4
1 <= n_i, k_i <= 10^4

How to solve Count Ways to Make Array With Product

An array with product k is determined by how each prime's exponent is split across the n positions. For a prime with exponent e that is a stars-and-bars count, C(n - 1 + e, e), and the primes are independent so the counts multiply.

Approach

Precompute inverse factorials for exponents up to 13 — no exponent exceeds that below 10⁴.
For each query, trial-divide k up to its square root, collecting each prime's exponent.
For each exponent e, multiply in C(n - 1 + e, e), computed as n · (n+1) · … · (n+e-1) · invFact[e].
If a prime factor above the square root remains, it has exponent 1 and contributes a factor of n.

Why it works

Independence across primes is what turns a product constraint into a product of counts: choosing where the 2s go never restricts where the 3s go. Computing the binomial from the falling product rather than a full factorial table is what keeps it cheap — the exponent is at most 13, so each binomial is a dozen multiplications and one small inverse.

Complexity

Time — O(q · √k)
Space — O(1) beyond the answers

Pitfalls

k = 1 has no primes, so the answer is 1 — the all-ones array.
A leftover factor above √k is prime with exponent 1, contributing C(n, 1) = n.
The binomial's top is n - 1 + e; using n + e counts an extra slot that does not exist.

Reference solution

Python

from typing import List

def waysToFillArray(queries: List[List[int]]) -> List[int]:
    MOD = 10**9 + 7
    MAXE = 14
    fact = [1] * (MAXE + 1)
    for i in range(1, MAXE + 1):
        fact[i] = fact[i - 1] * i % MOD
    inv_fact = [1] * (MAXE + 1)
    inv_fact[MAXE] = pow(fact[MAXE], MOD - 2, MOD)
    for i in range(MAXE, 0, -1):
        inv_fact[i - 1] = inv_fact[i] * i % MOD
    out = []
    for n, k in queries:
        answer = 1
        p = 2
        while p * p <= k:
            if k % p == 0:
                e = 0
                while k % p == 0:
                    k //= p
                    e += 1
                num = 1
                for t in range(e):
                    num = num * ((n + t) % MOD) % MOD
                answer = answer * (num * inv_fact[e] % MOD) % MOD
            p += 1
        if k > 1:
            answer = answer * (n % MOD) % MOD
        out.append(answer)
    return out

JavaScript

var waysToFillArray = function(queries) {
    var MOD = 1000000007, i;
    var mulmod = function(a, b) {
        var hi = Math.floor(a / 65536), lo = a % 65536;
        return ((hi * b % MOD) * 65536 + lo * b) % MOD;
    };
    var powmod = function(base, exp) {
        var result = 1, bb = base % MOD, e = exp;
        while (e > 0) {
            if (e % 2 === 1) result = mulmod(result, bb);
            bb = mulmod(bb, bb);
            e = Math.floor(e / 2);
        }
        return result;
    };
    var MAXE = 14;
    var fact = [1];
    for (i = 1; i <= MAXE; i++) fact.push(mulmod(fact[i - 1], i));
    var invFact = [];
    for (i = 0; i <= MAXE; i++) invFact.push(1);
    invFact[MAXE] = powmod(fact[MAXE], MOD - 2);
    for (i = MAXE; i >= 1; i--) invFact[i - 1] = mulmod(invFact[i], i);
    var out = [];
    for (var q = 0; q < queries.length; q++) {
        var n = queries[q][0], k = queries[q][1], answer = 1;
        for (var p = 2; p * p <= k; p++) {
            if (k % p !== 0) continue;
            var e = 0;
            while (k % p === 0) { k = k / p; e++; }
            var num = 1;
            for (var t = 0; t < e; t++) num = mulmod(num, (n + t) % MOD);
            answer = mulmod(answer, mulmod(num, invFact[e]));
        }
        if (k > 1) answer = mulmod(answer, n % MOD);
        out.push(answer);
    }
    return out;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue