We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Ways to Make Array With Product

Number: 1836

Difficulty: Hard

Paid? No

Companies: Amazon

Problem Description

Given a list of queries where each query is represented as [n, k], the goal is to count the number of ways to fill an array of size n with positive integers such that the product of the elements equals k. Since these counts can be very large, the answer for each query should be returned modulo 10^9+7.

Key Insights

  • The problem can be reduced to a combinatorial one by factorizing k into its prime factors.
  • For each prime factor p with exponent e in the factorization of k, we need to distribute e occurrences among n numbers. This is equivalent to finding the number of nonnegative integer solutions to a1 + a2 + … + an = e, which equals C(e + n – 1, n – 1) (stars and bars theorem).
  • The final answer for a query is the product (over all prime factors) of the combinations computed for each prime factor.
  • Precomputation of factorials and modular inverses (using Fermat’s little theorem, as the modulus is prime) will be used to efficiently compute binomial coefficients.
  • Factorizing k has a worst-case complexity of about O(√k), which is acceptable given the constraints.

Space and Time Complexity

Time Complexity: O(Q * √k + P) where Q is the number of queries (up to 10^4), k is at most 10^4, and P is the cost for precomputing factorials (precompute up to around 20000). Space Complexity: O(max_factorial_value) for storing factorials and modular inverses, which is roughly O(20000).

Solution

The solution first precomputes the necessary factorials and their modular inverses up to a predefined maximum (ensuring it covers the maximum possible value for n + exponent). For each query, the number k is factorized, and for each factor with exponent e, the number of distributions among n numbers is computed using the combination formula:   C(n + e - 1, n - 1). The overall result for the query is the product of these combination values (taken modulo 10^9+7). This approach leverages stars and bars (combinatorial distribution) and modular arithmetic to handle the large numbers.

Code Solutions

# Python Code
MOD = 10**9 + 7

# Precompute factorial and inverse factorial arrays up to MAX
MAX = 20000
fact = [1] * (MAX + 1)
invFact = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD

# Fermat's little theorem for modular inverse since MOD is prime
invFact[MAX] = pow(fact[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    invFact[i - 1] = invFact[i] * i % MOD

def nCr(n, r):
    if r < 0 or r > n:
        return 0
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD

def prime_factors(x):
    factors = {}
    d = 2
    while d * d <= x:
        while x % d == 0:
            factors[d] = factors.get(d, 0) + 1
            x //= d
        d += 1
    if x > 1:
        factors[x] = factors.get(x, 0) + 1
    return factors

def waysToFillArray(queries):
    results = []
    for n, k in queries:
        factors = prime_factors(k)
        ways = 1
        # for each prime factor, distribute the exponent among n numbers
        for exp in factors.values():
            ways = ways * nCr(n + exp - 1, n - 1) % MOD
        results.append(ways)
    return results

# Example usage:
queries = [[2,6],[5,1],[73,660]]
print(waysToFillArray(queries))  # Expected output: [4, 1, 50734910]
← Back to All Questions