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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Count Ways to Make Array With Product

Difficulty: Hard

Problem Description

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 array answer where answer.length == queries.length, and answer[i] is the answer to the ith query.

Key Insights

  • The product of the integers must equal ki, and we need to fill an array of size ni.
  • Each integer must be a positive divisor of ki.
  • The problem can be approached using combinatorial mathematics, specifically with the use of prime factorization.
  • The number of distinct arrangements can be calculated using multinomial coefficients based on the prime factor counts.

Space and Time Complexity

Time Complexity: O(q * (log(k) + n)), where q is the number of queries, k is the maximum value of ki, and n is the maximum value of ni.

Space Complexity: O(n + k), mainly for storing factorial values and results.

Solution

To solve the problem, we can use the following steps:

  1. Factorize ki into its prime factors and count the occurrences of each prime factor.
  2. For each prime factor with its count, calculate the number of ways to distribute these factors across ni positions in the array using the formula for combinations.
  3. Use precomputed factorial values to efficiently compute the combinations and apply modular arithmetic to handle large numbers.

Code Solutions

def count_ways(queries):
    MOD = 10**9 + 7
    
    def prime_factors(n):
        factors = {}
        d = 2
        while d * d <= n:
            while (n % d) == 0:
                if d in factors:
                    factors[d] += 1
                else:
                    factors[d] = 1
                n //= d
            d += 1
        if n > 1:
            factors[n] = 1
        return factors

    def precompute_factorials(max_n):
        fact = [1] * (max_n + 1)
        for i in range(2, max_n + 1):
            fact[i] = fact[i - 1] * i % MOD
        return fact

    def combinations(n, k):
        if k > n:
            return 0
        return (fact[n] * pow(fact[k], MOD - 2, MOD) * pow(fact[n - k], MOD - 2, MOD)) % MOD

    max_n = max(n for n, k in queries)
    fact = precompute_factorials(max_n)
    
    result = []
    for n, k in queries:
        if k == 1:
            result.append(1)
            continue
        
        factors = prime_factors(k)
        total_ways = 1
        
        for prime, count in factors.items():
            total_ways *= combinations(n + count - 1, count)  # Stars and Bars theorem
            total_ways %= MOD
        
        result.append(total_ways)
    
    return result
← Back to All Questions