Formatted question description: https://leetcode.ca/all/1735.html

1735. Count Ways to Make Array With Product

Level

Hard

Description

You are given a 2D integer array, queries. For each queries[i], where queries[i] = [n_i, k_i], 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 k_i. As the number of ways may be too large, the answer to the i-th 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 i-th query.

Example 1:

Input: queries = [2,6,5,1,73,660]

Output: [4,1,50734910]

Explanation: Each query is independent.

Example 2:

Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]

Output: [1,2,3,10,5]

Constraints:

• 1 <= queries.length <= 10^4
• 1 <= n_i, k_i <= 10^4

Solution

First, get all combination numbers for all possible values of n and k. Next, for each query (n, k), do prime factorization for k and calculate the number of ways using the combination numbers and the prime factorization results of k.

class Solution {
    int[] primes = new int[14];
    int[] exponents = new int[14];
    int index = 0;
    long[][] combinations = new long[11000][20];
    static final int MODULO = 1000000007;

    public int[] waysToFillArray(int[][] queries) {
        for (int i = 0; i < 10500; i++) {
            combinations[i][0] = 1;
            if (i < 15)
                combinations[i][i] = 1;
            int end = Math.min(i, 15);
            for (int j = 1; j < end; j++)
                combinations[i][j] = (combinations[i - 1][j - 1] + combinations[i - 1][j]) % MODULO;
        }
        int queriesCount = queries.length;
        int[] ways = new int[queriesCount];
        for (int i = 0; i < queriesCount; i++) {
            int n = queries[i][0], k = queries[i][1];
            long way = 1;
            fact(k);
            for (int j = 1; j <= index; j++)
                way = way * combinations[n + exponents[j] - 1][exponents[j]] % MODULO;
            ways[i] = (int) way;
        }
        return ways;
    }

    public void fact(int n) {
        index = 0;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                index++;
                primes[index] = i;
                exponents[index] = 0;
                while (n % i == 0) {
                    exponents[index]++;
                    n /= i;
                }
            }
        }
        if (n != 1) {
            index++;
            primes[index] = n;
            exponents[index] = 1;
        }
    }
}

All Problems

All Solutions