1836. Count Ways to Make Array With Product
My accepted Python solution to LeetCode problem 1836, Count Ways to Make Array With Product, running in 191ms.
- Difficulty: Hard
- Python
- Runtime 191ms
- Memory 21.7MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
Python
Accepted on LeetCode — runtime 191ms, memory 21.7MB, accepted 2025-12-29.
class Solution:
def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
MOD = 10**9 + 7
MAX_VAL = 10001
# Precompute smallest prime factor
spf = list(range(MAX_VAL))
for i in range(2, int(MAX_VAL**0.5) + 1):
if spf[i] == i:
for j in range(i*i, MAX_VAL, i):
if spf[j] == j:
spf[j] = i
# Precompute factorials and inverse factorials
MAX_COMB = 10015
fact = [1] * MAX_COMB
for i in range(1, MAX_COMB):
fact[i] = fact[i-1] * i % MOD
inv_fact = [1] * MAX_COMB
inv_fact[MAX_COMB-1] = pow(fact[MAX_COMB-1], MOD-2, MOD)
for i in range(MAX_COMB-2, -1, -1):
inv_fact[i] = inv_fact[i+1] * (i+1) % MOD
def comb(n, r):
if r < 0 or r > n:
return 0
return fact[n] * inv_fact[r] % MOD * inv_fact[n-r] % MOD
def factorize(k):
factors = []
while k > 1:
p = spf[k]
cnt = 0
while k % p == 0:
k //= p
cnt += 1
factors.append(cnt)
return factors
result = []
for n, k in queries:
factors = factorize(k)
ways = 1
for cnt in factors:
ways = ways * comb(n - 1 + cnt, cnt) % MOD
result.append(ways)
return result