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.
- Difficulty: Hard
- Topics: Arrays, Dynamic Programming, Math, 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^41 <= n_i, k_i <= 10^4
Hints for Count Ways to Make Array With Product
Hint 1
Factorise
k. Each prime's exponent is distributed across thenslots independently.Hint 2
Spreading
eidentical factors overnordered slots is stars and bars:C(n - 1 + e, e).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
- Precompute inverse factorials for exponents up to 13 — no exponent exceeds that below 10⁴.
- For each query, trial-divide
kup to its square root, collecting each prime's exponent. - For each exponent
e, multiply inC(n - 1 + e, e), computed asn · (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 = 1has 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; usingn + ecounts 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 outJava
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