Count Ways to Make Array With Product

Hard
1098.

Count Ways to Make Array With Product

Count Ways to Make Array With Product is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Microsoft interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} queries
 * @return {number[]}
 */
var waysToFillArray = function(queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Ways to Make Array With Product — Problem & Solution

Count Ways to Make Array With Product solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Count Ways to Make Array With Product is a hard coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Microsoft interviews.

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

Hints for Count Ways to Make Array With Product

  1. Hint 1

    Factorise k. Each prime's exponent is distributed across the n slots independently.

  2. Hint 2

    Spreading e identical factors over n ordered slots is stars and bars: C(n - 1 + e, e).

  3. Hint 3

    Multiply those binomials across the primes of k.

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

  1. Precompute inverse factorials for exponents up to 13 — no exponent exceeds that below 10⁴.
  2. For each query, trial-divide k up to its square root, collecting each prime's exponent.
  3. For each exponent e, multiply in C(n - 1 + e, e), computed as n · (n+1) · … · (n+e-1) · invFact[e].
  4. 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

Java

public static int[] waysToFillArray(int[][] queries) {
    final long MOD = 1000000007L;
    final int MAXE = 14;
    long[] fact = new long[MAXE + 1];
    fact[0] = 1;
    for (int i = 1; i <= MAXE; i++) fact[i] = fact[i - 1] * i % MOD;
    long[] invFact = new long[MAXE + 1];
    long base = fact[MAXE], e = MOD - 2, cur = 1;
    while (e > 0) {
        if ((e & 1L) == 1L) cur = cur * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    invFact[MAXE] = cur;
    for (int i = MAXE; i >= 1; i--) invFact[i - 1] = invFact[i] * i % MOD;
    int[] out = new int[queries.length];
    for (int q = 0; q < queries.length; q++) {
        int n = queries[q][0], k = queries[q][1];
        long answer = 1;
        for (int p = 2; (long) p * p <= k; p++) {
            if (k % p != 0) continue;
            int exp = 0;
            while (k % p == 0) {
                k /= p;
                exp++;
            }
            long num = 1;
            for (int t = 0; t < exp; t++) num = num * ((n + t) % MOD) % MOD;
            answer = answer * (num * invFact[exp] % MOD) % MOD;
        }
        if (k > 1) answer = answer * (n % MOD) % MOD;
        out[q] = (int) answer;
    }
    return out;
}

C++

vector<int> waysToFillArray(vector<vector<int>>& queries) {
    const long long MOD = 1000000007LL;
    const int MAXE = 14;
    vector<long long> fact(MAXE + 1, 1), invFact(MAXE + 1, 1);
    for (int i = 1; i <= MAXE; i++) fact[i] = fact[i - 1] * i % MOD;
    long long base = fact[MAXE], e = MOD - 2, cur = 1;
    while (e > 0) {
        if (e & 1LL) cur = cur * base % MOD;
        base = base * base % MOD;
        e >>= 1;
    }
    invFact[MAXE] = cur;
    for (int i = MAXE; i >= 1; i--) invFact[i - 1] = invFact[i] * i % MOD;
    vector<int> out;
    for (auto& q : queries) {
        int n = q[0], k = q[1];
        long long answer = 1;
        for (int p = 2; (long long) p * p <= k; p++) {
            if (k % p != 0) continue;
            int exp = 0;
            while (k % p == 0) {
                k /= p;
                exp++;
            }
            long long num = 1;
            for (int t = 0; t < exp; t++) num = num * ((n + t) % MOD) % MOD;
            answer = answer * (num * invFact[exp] % MOD) % MOD;
        }
        if (k > 1) answer = answer * (n % MOD) % MOD;
        out.push_back((int) 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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming