LeetCode 1735 - Count Ways to Make Array With Product

LeetCode Problem 1735

Difficulty: 🔴 Hard
Topics: Array, Math, Dynamic Programming, Combinatorics, Number Theory

Solution

Problem Understanding

The problem asks us to count the number of ways to fill an array of size ni with positive integers such that the product of all elements equals ki. Each query in the input array queries is independent, meaning we compute the answer for each (ni, ki) pair separately. The output is an array where each element corresponds to the number of valid arrays for the corresponding query, modulo 10^9 + 7 due to potentially large results.

The input queries is a 2D array where each element [ni, ki] represents the size of the array and the target product, respectively. The constraints 1 <= ni, ki <= 10^4 indicate that brute-force enumeration of all arrays is infeasible. We need a mathematical or combinatorial approach. Edge cases to consider include arrays where ki = 1 (all elements must be 1) and prime numbers ki (limited factorization options).

The problem guarantees that all numbers are positive integers, so zero or negative numbers do not appear, and ni and ki are at least 1.

Approaches

A brute-force approach would attempt to enumerate all sequences of size ni with product ki. This is clearly infeasible because even for small ni and ki, the number of possible sequences grows exponentially, e.g., for ni = 10 and ki = 100, there are thousands of possible combinations. Therefore, this approach will fail for the upper limits of 10^4.

The optimal approach leverages prime factorization and combinatorics. The key insight is to factorize ki into primes, e.g., ki = 2^a * 3^b * 5^c .... For each prime factor, distributing its exponent among ni array elements is equivalent to a stars and bars problem, where the number of non-negative integer solutions to x1 + x2 + ... + x_ni = exponent is given by the binomial coefficient C(exponent + ni - 1, ni - 1). Multiplying these counts for all prime factors gives the total number of ways to form arrays. We compute everything modulo 10^9 + 7.

Algorithm Walkthrough

1. Precompute factorials and modular inverses: To efficiently compute binomial coefficients modulo 10^9 + 7, precompute factorials and inverse factorials up to the maximum possible value of ni + max exponent (≤ 2*10^4 for constraints). Use Fermat's little theorem to compute modular inverses.
2. Prime factorization of ki: For each query (ni, ki), factorize ki into its prime components. This can be done efficiently up to √ki.
3. Stars and bars computation: For each prime factor with exponent e, calculate the number of ways to distribute e identical items among ni bins: C(e + ni - 1, ni - 1). Multiply the results for all prime factors modulo 10^9 + 7.
4. Aggregate results: Store the product of combinatorial counts for each query in the output array.

Why it works: Prime factorization reduces the problem of multiplying numbers to distributing prime powers among array positions. The stars and bars formula guarantees all non-negative integer solutions are counted exactly once. Multiplying results across primes ensures the product of the array equals ki.

Python Solution

from typing import List

MOD = 10**9 + 7
MAX = 20000  # sufficiently large for factorials

# Precompute factorials and inverses
fact = [1] * (MAX + 1)
inv_fact = [1] * (MAX + 1)

for i in range(1, MAX + 1):
    fact[i] = fact[i - 1] * i % MOD

inv_fact[MAX] = pow(fact[MAX], MOD - 2, MOD)
for i in range(MAX, 0, -1):
    inv_fact[i - 1] = inv_fact[i] * i % MOD

def comb(n: int, k: int) -> int:
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD

class Solution:
    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
        def prime_factors(x: int) -> List[int]:
            factors = []
            d = 2
            while d * d <= x:
                count = 0
                while x % d == 0:
                    x //= d
                    count += 1
                if count:
                    factors.append(count)
                d += 1
            if x > 1:
                factors.append(1)
            return factors

        result = []
        for n, k in queries:
            counts = prime_factors(k)
            ways = 1
            for e in counts:
                ways = ways * comb(e + n - 1, n - 1) % MOD
            result.append(ways)
        return result

The code first precomputes factorials and inverse factorials for modular binomial coefficient calculations. For each query, it factorizes ki, applies stars and bars to each exponent, multiplies the results modulo 10^9 + 7, and appends to the result list.

Go Solution

package main

const MOD int = 1e9 + 7
const MAX int = 20000

var fact [MAX + 1]int
var invFact [MAX + 1]int

func initFactorials() {
    fact[0] = 1
    for i := 1; i <= MAX; i++ {
        fact[i] = fact[i-1] * i % MOD
    }
    invFact[MAX] = pow(fact[MAX], MOD-2)
    for i := MAX; i > 0; i-- {
        invFact[i-1] = invFact[i] * i % MOD
    }
}

func pow(a, b int) int {
    res := 1
    for b > 0 {
        if b&1 == 1 {
            res = res * a % MOD
        }
        a = a * a % MOD
        b >>= 1
    }
    return res
}

func comb(n, k int) int {
    if k < 0 || k > n {
        return 0
    }
    return fact[n] * invFact[k] % MOD * invFact[n-k] % MOD
}

func primeFactors(x int) []int {
    factors := []int{}
    for d := 2; d*d <= x; d++ {
        count := 0
        for x%d == 0 {
            x /= d
            count++
        }
        if count > 0 {
            factors = append(factors, count)
        }
    }
    if x > 1 {
        factors = append(factors, 1)
    }
    return factors
}

func waysToFillArray(queries [][]int) []int {
    initFactorials()
    res := make([]int, len(queries))
    for i, q := range queries {
        n, k := q[0], q[1]
        counts := primeFactors(k)
        ways := 1
        for _, e := range counts {
            ways = ways * comb(e+n-1, n-1) % MOD
        }
        res[i] = ways
    }
    return res
}

Go handles slices and integer multiplication modulo MOD. initFactorials is called once to prepare combinatorial computations, and primeFactors returns a slice of exponents. The main function aggregates results similarly to Python.

Worked Examples

Example [[2,6],[5,1],[73,660]]:

Query (2,6) prime factors: 6 = 2^1 * 3^1. Ways = C(1+2-1, 2-1) * C(1+2-1,2-1) = C(2,1)*C(2,1)=2*2=4.

Query (5,1) prime factors: 1 has no prime factors, implicitly 0 exponents. Ways = 1 (all 1s).

Query (73,660) prime factors: 660 = 2^2 * 3^1 * 5^1 * 11^1. Ways = C(2+73-1,72)*C(1+73-1,72)^3. Compute modulo 10^9 + 7 = 50734910.

Complexity Analysis

The algorithm efficiently scales to maximum