1735. Count Ways to Make Array With Product - Leetcode Solution

Problem Description

You are given two integers: n and k. Your task is to count the number of different arrays of length n such that the product of all the elements in the array is exactly k. Each element in the array must be a positive integer (greater than 0). The answer should be returned modulo 10^9 + 7.

Each element can be any positive integer.
The order of elements in the array matters (different orderings count as different arrays).
Elements may be repeated.
You must find the total number of arrays, not the arrays themselves.

Constraints:

1 ≤ n ≤ 100
1 ≤ k ≤ 10⁴

Thought Process

At first glance, one might try to generate all possible arrays of length n, check their product, and count those that equal k. However, this quickly becomes unfeasible as the number of possible arrays grows exponentially with n and k. We need a more efficient way to count the arrays without generating them.

The key realization is that the product of the array elements must be exactly k. Since elements are positive integers, we can think in terms of the prime factorization of k. Each element in the array will contribute some of these prime factors. The problem reduces to distributing the prime factors of k among n slots (array elements).

This is a classic combinatorics problem, where we count the number of non-negative integer solutions to a sum, which can be solved with the "stars and bars" method.

Solution Approach

Let's break down the solution step-by-step:

Prime Factorize k:
- Express k as a product of its prime factors: k = p1^a1 * p2^a2 * ... * pm^am.
Distribute Exponents:
- For each prime pi with exponent ai, we need to distribute ai indistinguishable objects (prime factors) into n distinguishable bins (array elements).
- The number of ways to do this is C(ai + n - 1, n - 1), where C is the binomial coefficient.
Combine Choices:
- The total number of arrays is the product of the ways for each prime factor, since the distributions are independent.
Modulo Arithmetic:
- Since the answer can be very large, perform all calculations modulo 10^9 + 7.
Efficient Computation:
- Precompute factorials and inverse factorials up to n + max exponent for efficient binomial coefficient calculation.

By using combinatorics and prime factorization, we avoid brute-force enumeration and achieve an efficient solution.

Example Walkthrough

Let's consider n = 3 and k = 6.

Prime factorize 6: 6 = 2^1 * 3^1.
We need to distribute 1 "2" and 1 "3" among 3 elements.
For "2": Number of ways to distribute 1 indistinguishable "2" among 3 slots = C(1 + 3 - 1, 3 - 1) = C(3, 2) = 3.
For "3": Number of ways to distribute 1 indistinguishable "3" among 3 slots = C(3, 2) = 3.
Total number of arrays = 3 * 3 = 9.

The valid arrays (with their products) are:

[6,1,1], [1,6,1], [1,1,6]
[2,3,1], [2,1,3], [1,2,3], [3,2,1], [3,1,2], [1,3,2]

All 9 arrays have product 6.

Time and Space Complexity

Brute-force approach:
- Would try all possible arrays of length n with elements from 1 to k.
- Time complexity: O(k^n) (infeasible for large n).
Optimized approach:
- Prime factorization of k: O(√k).
- For each prime, compute binomial coefficients: O(n + max exponent) for precomputing factorials, and O(number of prime factors) for the product.
- Overall time: O(√k + n + log k) (since the number of primes is at most log k).
- Space: O(n + max exponent) for factorials.

Summary

The problem of counting arrays with a given product is elegantly solved by recognizing it as a combinatorial distribution of prime factors. By prime factorizing k and using the stars and bars method for each exponent, we efficiently count the number of valid arrays. Precomputing factorials allows for fast binomial coefficient calculation, making the solution both efficient and scalable.

Code Implementation

MOD = 10**9 + 7

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

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

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

def waysToFillArray(queries):
    res = []
    max_n = max(n for n, k in queries)
    max_k = max(k for n, k in queries)
    # Maximum possible exponent is log2(max_k) * max_n
    fact, inv = precompute_factorials(100 + 14 * 100)
    for n, k in queries:
        factors = prime_factors(k)
        ans = 1
        for p, exp in factors.items():
            ans = ans * comb(exp + n - 1, n - 1, fact, inv) % MOD
        res.append(ans)
    return res

# Example usage:
# queries = [(3, 6)]
# print(waysToFillArray(queries))  # Output: [9]

#include <vector>
#include <unordered_map>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX = 2000;

vector<long long> fact(MAX+1, 1), inv(MAX+1, 1);

long long mod_pow(long long x, long long y, int mod) {
    long long res = 1;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

void precompute() {
    for (int i = 1; i <= MAX; ++i)
        fact[i] = fact[i-1] * i % MOD;
    inv[MAX] = mod_pow(fact[MAX], MOD-2, MOD);
    for (int i = MAX-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;
}

unordered_map<int, int> prime_factors(int k) {
    unordered_map<int, int> factors;
    for (int d = 2; d * d <= k; ++d) {
        while (k % d == 0) {
            factors[d]++;
            k /= d;
        }
    }
    if (k > 1) factors[k]++;
    return factors;
}

vector<int> waysToFillArray(vector<pair<int, int>>& queries) {
    precompute();
    vector<int> res;
    for (auto& q : queries) {
        int n = q.first, k = q.second;
        auto factors = prime_factors(k);
        long long ans = 1;
        for (auto& f : factors) {
            int exp = f.second;
            ans = ans * comb(exp + n - 1, n - 1) % MOD;
        }
        res.push_back(ans);
    }
    return res;
}

// Example usage:
// vector<pair<int, int>> queries = {{3, 6}};
// auto result = waysToFillArray(queries); // result[0] == 9

import java.util.*;

public class Solution {
    static final int MOD = 1000000007;
    static final int MAX = 2000;
    static long[] fact = new long[MAX+1];
    static long[] inv = new long[MAX+1];

    static {
        fact[0] = 1;
        for (int i = 1; i <= MAX; i++) fact[i] = fact[i-1] * i % MOD;
        inv[MAX] = pow(fact[MAX], MOD-2);
        for (int i = MAX-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
    }

    static long pow(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;
    }

    static Map<Integer, Integer> primeFactors(int k) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int d = 2; d * d <= k; d++) {
            while (k % d == 0) {
                map.put(d, map.getOrDefault(d, 0) + 1);
                k /= d;
            }
        }
        if (k > 1) map.put(k, map.getOrDefault(k, 0) + 1);
        return map;
    }

    static 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) {
        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int n = queries[i][0], k = queries[i][1];
            Map<Integer, Integer> factors = primeFactors(k);
            long ans = 1;
            for (int exp : factors.values()) {
                ans = ans * comb(exp + n - 1, n - 1) % MOD;
            }
            res[i] = (int)ans;
        }
        return res;
    }

    // Example usage:
    // int[][] queries = {{3, 6}};
    // System.out.println(Arrays.toString(new Solution().waysToFillArray(queries))); // [9]
}

const MOD = 1e9 + 7;
const MAX = 2000;

function precomputeFactorials(limit) {
    const fact = new Array(limit + 1).fill(1);
    const inv = new Array(limit + 1).fill(1);
    for (let i = 1; i <= limit; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    inv[limit] = pow(fact[limit], MOD-2);
    for (let i = limit-1; i >= 0; i--) {
        inv[i] = inv[i+1] * (i+1) % MOD;
    }
    return [fact, inv];
}

function pow(a, b) {
    let res = 1, base = a % MOD;
    while (b > 0) {
        if (b & 1) res = res * base % MOD;
        base = base * base % MOD;
        b >>= 1;
    }
    return res;
}

function primeFactors(k) {
    const map = new Map();
    let d = 2;
    while (d * d <= k) {
        let cnt = 0;
        while (k % d === 0) {
            cnt++;
            k = Math.floor(k / d);
        }
        if (cnt) map.set(d, cnt);
        d++;
    }
    if (k > 1) map.set(k, 1);
    return map;
}

function comb(n, k, fact, inv) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv[k] % MOD * inv[n-k] % MOD;
}

function waysToFillArray(queries) {
    let maxN = 0, maxK = 0;
    for (const [n, k] of queries) {
        maxN = Math.max(maxN, n);
        maxK = Math.max(maxK, k);
    }
    const [fact, inv] = precomputeFactorials(MAX);
    const res = [];
    for (const [n, k] of queries) {
        const factors = primeFactors(k);
        let ans = 1;
        for (const exp of factors.values()) {
            ans = ans * comb(exp + n - 1, n - 1, fact, inv) % MOD;
        }
        res.push(ans);
    }
    return res;
}

// Example usage:
// console.log(waysToFillArray([[3, 6]])); // [9]

AlgoMap.io

Want Help Cracking FAANG?