Count Ways to Make Array With Product
HardUpdated: Aug 2, 2025
Practice on:
Problem
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 10^9 + 7.
Return an integer arrayanswer whereanswer.length == queries.length , andanswer[i]is the answer to theith query.
Examples
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 10^9 + 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 <= 10^41 <= ni, ki <= 10^4
Solution
Method 1 – Prime Factorization + Stars and Bars (Combinatorics)
Intuition
The key idea is to break down the product ki into its prime factors. For each prime factor, we need to distribute its total exponent among ni slots (array elements). This is a classic combinatorics problem (stars and bars): the number of ways to distribute e identical items into n bins is C(n+e-1, e). The answer for each query is the product of such combinations for all prime factors of ki.
Approach
- Precompute factorials and inverse factorials up to the maximum possible value (2 * 10^4) for efficient nCr calculation modulo 1e9+7.
- For each query [n, k]:
- Factorize
kinto its prime factors and their exponents. - For each prime factor with exponent
e, compute C(n+e-1, e). - Multiply all such combinations for all prime factors.
- Factorize
- Return the result for each query.
Code
C++
class Solution {
public:
static constexpr int MOD = 1e9 + 7;
vector<long long> fact, inv;
long long power(long long a, long long b) {
long long res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void build(int N) {
fact.resize(N+1, 1);
inv.resize(N+1, 1);
for (int i = 1; i <= N; ++i) fact[i] = fact[i-1] * i % MOD;
inv[N] = power(fact[N], MOD-2);
for (int i = N-1; i >= 0; --i) inv[i] = inv[i+1] * (i+1) % MOD;
}
long long comb(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * inv[k] % MOD * inv[n-k] % MOD;
}
vector<int> waysToFillArray(vector<vector<int>>& queries) {
build(20000);
vector<int> ans;
for (auto& q : queries) {
int n = q[0], k = q[1];
long long res = 1;
for (int d = 2; d * d <= k; ++d) {
int cnt = 0;
while (k % d == 0) {
k /= d;
++cnt;
}
if (cnt) res = res * comb(n+cnt-1, cnt) % MOD;
}
if (k > 1) res = res * comb(n, 1) % MOD;
ans.push_back(res);
}
return ans;
}
};
Go
func waysToFillArray(queries [][]int) []int {
const mod = 1e9 + 7
N := 20000
fact := make([]int, N+1)
inv := make([]int, N+1)
fact[0] = 1
for i := 1; i <= N; i++ {
fact[i] = fact[i-1] * i % mod
}
inv[N] = pow(fact[N], mod-2, mod)
for i := N-1; i >= 0; i-- {
inv[i] = inv[i+1] * (i+1) % mod
}
comb := func(n, k int) int {
if k < 0 || k > n {
return 0
}
return fact[n] * inv[k] % mod * inv[n-k] % mod
}
pow := func(a, b, m int) int {
res := 1
for b > 0 {
if b&1 == 1 {
res = res * a % m
}
a = a * a % m
b >>= 1
}
return res
}
ans := make([]int, len(queries))
for i, q := range queries {
n, k := q[0], q[1]
res := 1
for d := 2; d*d <= k; d++ {
cnt := 0
for k%d == 0 {
k /= d
cnt++
}
if cnt > 0 {
res = res * comb(n+cnt-1, cnt) % mod
}
}
if k > 1 {
res = res * comb(n, 1) % mod
}
ans[i] = res
}
return ans
}
Java
class Solution {
static final int MOD = 1_000_000_7;
long[] fact, inv;
long power(long a, long b) {
long res = 1;
while (b > 0) {
if ((b & 1) == 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
void build(int N) {
fact = new long[N+1];
inv = new long[N+1];
fact[0] = 1;
for (int i = 1; i <= N; i++) fact[i] = fact[i-1] * i % MOD;
inv[N] = power(fact[N], MOD-2);
for (int i = N-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
}
long comb(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * inv[k] % MOD * inv[n-k] % MOD;
}
public int[] waysToFillArray(int[][] queries) {
build(20000);
int[] ans = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int n = queries[i][0], k = queries[i][1];
long res = 1;
for (int d = 2; d * d <= k; d++) {
int cnt = 0;
while (k % d == 0) {
k /= d;
cnt++;
}
if (cnt > 0) res = res * comb(n+cnt-1, cnt) % MOD;
}
if (k > 1) res = res * comb(n, 1) % MOD;
ans[i] = (int) res;
}
return ans;
}
}
Kotlin
class Solution {
private val MOD = 1_000_000_7
private lateinit var fact: LongArray
private lateinit var inv: LongArray
private fun power(a: Long, b: Long): Long {
var a = a
var b = b
var res = 1L
while (b > 0) {
if (b and 1L == 1L) res = res * a % MOD
a = a * a % MOD
b = b shr 1
}
return res
}
private fun build(N: Int) {
fact = LongArray(N+1) { 1L }
inv = LongArray(N+1) { 1L }
for (i in 1..N) fact[i] = fact[i-1] * i % MOD
inv[N] = power(fact[N], MOD-2)
for (i in N-1 downTo 0) inv[i] = inv[i+1] * (i+1) % MOD
}
private fun comb(n: Int, k: Int): Long {
if (k < 0 || k > n) return 0L
return fact[n] * inv[k] % MOD * inv[n-k] % MOD
}
fun waysToFillArray(queries: Array<IntArray>): IntArray {
build(20000)
val ans = IntArray(queries.size)
for ((i, q) in queries.withIndex()) {
var n = q[0]
var k = q[1]
var res = 1L
var d = 2
while (d * d <= k) {
var cnt = 0
while (k % d == 0) {
k /= d
cnt++
}
if (cnt > 0) res = res * comb(n+cnt-1, cnt) % MOD
d++
}
if (k > 1) res = res * comb(n, 1) % MOD
ans[i] = res.toInt()
}
return ans
}
}
Python
class Solution:
def waysToFillArray(self, queries: list[list[int]]) -> list[int]:
MOD = 10**9 + 7
N = 20000
fact = [1] * (N+1)
inv = [1] * (N+1)
for i in range(1, N+1):
fact[i] = fact[i-1] * i % MOD
inv[N] = pow(fact[N], MOD-2, MOD)
for i in range(N-1, -1, -1):
inv[i] = inv[i+1] * (i+1) % MOD
def comb(n: int, k: int) -> int:
if k < 0 or k > n:
return 0
return fact[n] * inv[k] % MOD * inv[n-k] % MOD
ans = []
for n, k in queries:
res = 1
d = 2
while d * d <= k:
cnt = 0
while k % d == 0:
k //= d
cnt += 1
if cnt:
res = res * comb(n+cnt-1, cnt) % MOD
d += 1
if k > 1:
res = res * comb(n, 1) % MOD
ans.append(res)
return ans
Rust
impl Solution {
pub fn ways_to_fill_array(queries: Vec<Vec<i32>>) -> Vec<i32> {
const MOD: i64 = 1_000_000_007;
let n = 20000;
let mut fact = vec![1i64; n+1];
let mut inv = vec![1i64; n+1];
for i in 1..=n {
fact[i] = fact[i-1] * i as i64 % MOD;
}
inv[n] = pow(fact[n], MOD-2, MOD);
for i in (0..n).rev() {
inv[i] = inv[i+1] * (i as i64 + 1) % MOD;
}
fn pow(mut a: i64, mut b: i64, m: i64) -> i64 {
let mut res = 1;
while b > 0 {
if b & 1 == 1 {
res = res * a % m;
}
a = a * a % m;
b >>= 1;
}
res
}
fn comb(n: usize, k: usize, fact: &Vec<i64>, inv: &Vec<i64>) -> i64 {
if k > n { return 0; }
fact[n] * inv[k] % MOD * inv[n-k] % MOD
}
let mut ans = vec![];
for q in queries {
let (mut n, mut k) = (q[0] as usize, q[1] as i64);
let mut res = 1i64;
let mut d = 2i64;
while d * d <= k {
let mut cnt = 0;
while k % d == 0 {
k /= d;
cnt += 1;
}
if cnt > 0 {
res = res * comb(n+cnt-1, cnt, &fact, &inv) % MOD;
}
d += 1;
}
if k > 1 {
res = res * comb(n, 1, &fact, &inv) % MOD;
}
ans.push(res as i32);
}
ans
}
}
TypeScript
class Solution {
waysToFillArray(queries: number[][]): number[] {
const MOD = 1e9 + 7;
const N = 20000;
const fact: number[] = Array(N+1).fill(1);
const inv: number[] = Array(N+1).fill(1);
for (let i = 1; i <= N; i++) fact[i] = fact[i-1] * i % MOD;
inv[N] = pow(fact[N], MOD-2, MOD);
for (let i = N-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
function pow(a: number, b: number, m: number): number {
let res = 1;
while (b > 0) {
if (b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
function comb(n: number, k: number): number {
if (k < 0 || k > n) return 0;
return fact[n] * inv[k] % MOD * inv[n-k] % MOD;
}
const ans: number[] = [];
for (const [n, k0] of queries) {
let k = k0, res = 1;
for (let d = 2; d * d <= k; d++) {
let cnt = 0;
while (k % d === 0) {
k = Math.floor(k / d);
cnt++;
}
if (cnt) res = res * comb(n+cnt-1, cnt) % MOD;
}
if (k > 1) res = res * comb(n, 1) % MOD;
ans.push(res);
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(Q * sqrt(K) + N), where Q is the number of queries, K is the max value of ki, and N is the max value for factorial precomputation. - 🧺 Space complexity:
O(N), for factorial and inverse factorial arrays.