1735. Count Ways to Make Array With Product

HardArrayMathDynamic ProgrammingCombinatoricsNumber Theory
Leetcode Link

Problem Description

The given problem involves combinatorics and number theory. We are tasked with determining the number of distinct ways we can fill an array of length n such that the product of all the elements in the array equals a specific value k. The constraints that must be considered:

  • The array must contain only positive integers.
  • The order of the elements in the array matters, meaning different permutations of the same numbers count as separate ways.
  • The problem doesn't ask for the actual configurations but rather just the total count of these configurations.
  • The count can become very large, so we return the result modulo 10^9 + 7, a common practice to control the size of the output in combinatorial problems.

Each query queries[i] represents a separate instance of the problem with its own n and k.

We aim to return an array where each element is the solution to the corresponding query.

Intuition

The key to solve this problem is understanding how to break down the prime factors of k and utilize the stars-and-bars combinatorial method.

Here is the intuition behind the solution:

  1. If k can be factorized into prime factors (e.g., k = p1^a1 * p2^a2 * ... * pm^am), the problem then reduces to how we can distribute the a1 counts of p1, a2 counts of p2, and so on into n slots in the array.

  2. The problem, therefore, becomes one of partitioning each group of identical prime factors among the n slots, which is a typical scenario where the stars-and-bars theorem can be applied.

  3. Stars-and-bars is a well-known combinatorial method that can determine the number of ways N identical items can be placed into k distinct bins.

The formula derived from stars-and-bars is comb(n+k-1, n-1) which gives the count of ways we can insert k indistinguishable items into n bins.

  1. The prime factorization for each k is done once and used to calculate all requested combinations, to improve efficiency.

  2. The provided code uses dynamic programming to calculate the factorial of numbers and their modular inverses, which are essential for calculating combinations modulo 10^9 + 7.

  3. The function comb is used to apply the stars-and-bars theorem as discussed.

  4. The key point to understanding is that for each prime factor pi and its count ai, we have comb(ai+n-1, n-1) ways to distribute those prime factors into the n slots. Since the prime factors are independent of each other, we can multiply the results for each prime factor count to get the total count for k.

  5. Finally, the solution iteratively computes the result for each query by multiplying the combinations of distributions for each prime factor count, thereby giving the total number of ways to fill the array for each query.

Learn more about Math, Dynamic Programming and Combinatorics patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

Which of the following is a good use case for backtracking?

Solution Approach

The solution uses a combination of dynamic programming, number theory (prime factorization), and combinatorics (stars-and-bars theorem) to efficiently solve the problem. The implementation can be divided into several steps:

  1. Pre-computation of Factorials and Inverses:

    • The f array pre-computes and stores factorials modulo 10^9 + 7 up to a certain number N. This is given by the relation f[i] = f[i - 1] * i % MOD.
    • The g array stores the modular inverses of the factorials, which are precomputed using Fermat's Little Theorem. g[i] = pow(f[i], MOD - 2, MOD) gives the modular inverse of f[i].
    • Pre-computing these values allows constant-time access for calculating combinations later on.

  2. Prime Factorization:

    • A dictionary p is used to store the counts of the prime factors for each number less than N.
    • For each number i, divide it by its prime factors, count their occurrences, and store the counts in p[i].

  3. Calculating Combinations:

    • The comb function uses the pre-computed factorials and their inverses to calculate combinations. It follows the formula f[n] * g[k] * g[n - k] % MOD which provides C(n, k) modulo 10^9 + 7.

  4. Solution Class:

    • The Solution class contains the method waysToFillArray, which takes a list of queries as input and returns the counts of ways to fill arrays as required.
    • For each query [n, k], initialize a result variable t to 1. This variable will hold the product of combinations for each prime factor count.
    • Iterate over the prime factor counts for k stored in p[k], and for each count x, use the comb function to calculate the ways to distribute these prime factors into n slots. Multiply t by this number modulo MOD.
    • Append the final product t to the ans array after the inner loop. This t represents the answer to the query.

  5. Applying Stars-And-Bars Theorem:

    • For each prime factor count x, the problem of distribution corresponds to assigning x identical items to n distinct bins, which is where the stars-and-bars theorem comb(x + n - 1, n - 1) is applied.

  6. Modular Arithmetic:

    • Due to potentially large numbers and to abide by the problem statement, all calculations are done under modulo 10^9 + 7. This ensures that the resulting number stays within the limit of a 32-bit integer.

By combining these methods and following the solution step by step for each query, the solution approach effectively addresses the problem in a way that is optimized for time and space complexity.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27
1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30
1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

Example Walkthrough

Let's walk through a simple example to illustrate the solution approach. Suppose we have one query with n = 2 and k = 8. Our goal is to find the number of distinct ways we can fill an array of length n such that the product of all elements in the array equals k.

  1. First, let's do the prime factorization of k. Since k = 8, and 8 is 2^3, our prime factors are 2 with a count of 3.

  2. Using stars-and-bars, we need to find the number of ways to distribute these three 2s into the n slots. Using the theorem, we get the formula comb(3 + 2 - 1, 2 - 1) which calculates how to distribute 3 indistinguishable items (the prime factor 2 in this case) into 2 bins (the array slots).

  3. Using the combination function comb, we find comb(4, 1). We can assume f and g arrays have been pre-calculated so that f stores factorials modulo 10^9 + 7 and g stores the inverses of these factorials. Therefore, comb(4, 1) will use these precomputed values to efficiently calculate the result.

  4. The combination would be: f[4] * g[1] * g[4 - 1] % MOD. If we have precomputed values, let's say f[4] = 24, g[1] = 1, and g[3] = some_inverse_value, the result would be 24 * 1 * some_inverse_value % MOD.

  5. The result of this calculation gives us the count of ways we can distribute the prime factors of k into n slots. Since there's only one prime factor in this example, that result is the total count of ways to fill the array.

  6. We multiply all the combinations of distributions for each prime factor count. However, in this specific case, we only have one prime factor, so we don't need to multiply further.

  7. The final result is what we calculated from comb(4, 1), and that's the answer for the given query [n, k].

  8. All steps are performed using modular arithmetic to ensure that the output remains within the required bounds.

Applying the steps above, let's say we calculated the inverses and found that g[3] is some_inverse_value such that the product 24 * 1 * some_inverse_value % MOD equals 4. Therefore, for the query [2, 8], there are 4 distinct ways to fill the array such that the product of the elements is 8.

For a concrete answer, let's just indicate the combinations without considering the modulo operation:

  • Array [1, 8]: The elements' product is 1*8 = 8.
  • Array [2, 4]: The product is 2*4 = 8.
  • Array [4, 2]: Since order matters, this is different from [2, 4], so the product is 4*2 = 8.
  • Array [8, 1]: This is also different from [1, 8] and the product is 8*1 = 8.

Thus, there are indeed 4 distinct ways to fill the array.

Solution Implementation

1from collections import defaultdict
2from typing import List
3
4# Define the maximum number for which we will pre-calculate the factorials.
5MAX_N = 10020
6# Define the modulo for calculations.
7MOD = 10**9 + 7
8
9# Pre-calculate factorials and their modular inverses.
10factorials = [1] * MAX_N
11inverse_factorials = [1] * MAX_N
12prime_factors_counts = defaultdict(list)
13
14# Calculate the values for 'factorials' and 'inverse_factorials',
15# and also pre-calculate the exponents of prime factors for all numbers up to MAX_N.
16for i in range(1, MAX_N):
17    factorials[i] = factorials[i - 1] * i % MOD
18    inverse_factorials[i] = pow(factorials[i], MOD - 2, MOD)
19    x = i
20    j = 2
21    while j <= x // j:
22        if x % j == 0:
23            count = 0
24            while x % j == 0:
25                count += 1
26                x //= j
27            prime_factors_counts[i].append(count)
28        j += 1
29    if x > 1:
30        prime_factors_counts[i].append(1)
31
32# Define a combination function using the pre-computed factorials and modular inverses.
33def combination(n, k):
34    return factorials[n] * inverse_factorials[k] * inverse_factorials[n - k] % MOD
35
36class Solution:
37    def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
38        results = []
39        # For each query, calculate the number of ways to fill the array.
40        for n, k in queries:
41            total_ways = 1
42            # Use the counts of each prime factor to calculate combinations.
43            for exponent in prime_factors_counts[k]:
44                total_ways = total_ways * combination(exponent + n - 1, n - 1) % MOD
45            results.append(total_ways)
46        return results
47
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    private static final int MAX_VALUE = 10020; // Maximum value for pre-computation
7    private static final int MODULUS = (int) 1e9 + 7; // Modulus value for calculations to prevent overflow
8    private static final long[] factorial = new long[MAX_VALUE]; // Cache for factorial values
9    private static final long[] inverseFactorial = new long[MAX_VALUE]; // Cache for inverse factorial values
10    private static final List<Integer>[] primeFactorsCounts = new List[MAX_VALUE]; // Lists to store counts of prime factors for each number
11
12    // Pre-compute factorials, inverse factorials, and prime factors counts
13    static {
14        factorial[0] = 1;
15        inverseFactorial[0] = 1;
16        Arrays.setAll(primeFactorsCounts, k -> new ArrayList<>());
17        for (int i = 1; i < MAX_VALUE; ++i) {
18            factorial[i] = factorial[i - 1] * i % MODULUS;
19            inverseFactorial[i] = modInverse(factorial[i], MODULUS);
20            int x = i;
21            for (int j = 2; j <= x / j; ++j) {
22                if (x % j == 0) {
23                    int count = 0;
24                    while (x % j == 0) {
25                        count++;
26                        x /= j;
27                    }
28                    primeFactorsCounts[i].add(count);
29                }
30            }
31            if (x > 1) {
32                primeFactorsCounts[i].add(1);
33            }
34        }
35    }
36
37    // Calculate modular inverse using fast exponentiation
38    public static long modInverse(long a, long k, long p) {
39        long res = 1;
40        while (k != 0) {
41            if ((k & 1) == 1) {
42                res = res * a % p;
43            }
44            k >>= 1;
45            a = a * a % p;
46        }
47        return res;
48    }
49
50    // Function to calculate combination C(n, k) using precomputed factorials
51    public static long combination(int n, int k) {
52        return (factorial[n] * inverseFactorial[k] % MODULUS) * inverseFactorial[n - k] % MODULUS;
53    }
54
55    // Given an array of queries, calculate the number of ways to fill an array for each query
56    public int[] waysToFillArray(int[][] queries) {
57        int queryLength = queries.length;
58        int[] result = new int[queryLength];
59        for (int i = 0; i < queryLength; ++i) {
60            int n = queries[i][0], k = queries[i][1];
61            long totalWays = 1;
62            for (int primeFactorCount : primeFactorsCounts[k]) {
63                totalWays = totalWays * combination(primeFactorCount + n - 1, n - 1) % MODULUS;
64            }
65            result[i] = (int) totalWays;
66        }
67        return result;
68    }
69}
70
1#include <vector>
2using namespace std;
3
4const int MAX_N = 10020;
5const long MOD = 1e9 + 7;
6long factorial[MAX_N];
7long inverseFactorial[MAX_N];
8vector<int> primeFactors[MAX_N];
9
10// Quick Modulo Exponentiation Function
11long qmi(long base, long exponent, long modulus) {
12    long res = 1;
13    while (exponent != 0) {
14        if ((exponent & 1) == 1) {
15            res = res * base % modulus;
16        }
17        exponent >>= 1; // equivalent to exponent /= 2
18        base = base * base % modulus;
19    }
20    return res;
21}
22
23// Initialization of factorials and prime factors arrays (done once using a lambda function)
24int dummy = []() {
25    factorial[0] = 1;
26    inverseFactorial[0] = 1;
27    // Precompute factorials and their modular inverses
28    for (int i = 1; i < MAX_N; ++i) {
29        factorial[i] = factorial[i - 1] * i % MOD;
30        inverseFactorial[i] = qmi(factorial[i], MOD - 2, MOD);
31      
32        // Find and store prime factors for each number
33        int x = i;
34        for (int j = 2; j <= x / j; ++j) {
35            if (x % j == 0) {
36                int count = 0;
37                while (x % j == 0) {
38                    ++count;
39                    x /= j;
40                }
41                primeFactors[i].push_back(count);
42            }
43        }
44        if (x > 1) { // If there is a prime factor greater than 1
45            primeFactors[i].push_back(1);
46        }
47    }
48    return 0;
49}();
50
51// Compute binomial coefficient using the precomputed factorials and their inverses
52int comb(int n, int k) {
53    return (factorial[n] * inverseFactorial[k] % MOD) * inverseFactorial[n - k] % MOD;
54}
55
56class Solution {
57public:
58    vector<int> waysToFillArray(vector<vector<int>>& queries) {
59        vector<int> answer;
60        for (auto& q : queries) {
61            int n = q[0], k = q[1];
62            long long totalWays = 1;
63            // Calculate the total number of ways using the combinations of prime factors
64            for (int primeFactorCount : primeFactors[k]) {
65                totalWays = totalWays * comb(primeFactorCount + n - 1, n - 1) % MOD;
66            }
67            answer.push_back(totalWays);
68        }
69        return answer;
70    }
71};
72
1// Import statements required for the use of data structures like vectors are not required in TypeScript
2// Constants
3const MAX_N: number = 10020;
4const MOD: number = 1e9 + 7;
5
6// Arrays
7const factorial: number[] = new Array(MAX_N);
8const inverseFactorial: number[] = new Array(MAX_N);
9const primeFactors: number[][] = new Array(MAX_N).fill(null).map(() => []);
10
11// Quick Modulo Exponentiation Function
12const quickModInt = (base: number, exponent: number, modulus: number): number => {
13    let res: number = 1;
14    while (exponent !== 0) {
15        if ((exponent & 1) === 1) {
16            res = (res * base) % modulus;
17        }
18        exponent >>= 1; // equivalent to exponent /= 2
19        base = (base * base) % modulus;
20    }
21    return res;
22};
23
24// Anonymous function to initialize factorials and prime factors arrays
25const initialize = (() => {
26    factorial[0] = inverseFactorial[0] = 1;
27    for (let i = 1; i < MAX_N; ++i) {
28        factorial[i] = (factorial[i - 1] * i) % MOD;
29        inverseFactorial[i] = quickModInt(factorial[i], MOD - 2, MOD);
30
31        // Calculate prime factors for each number
32        let x = i;
33        for (let j = 2; j <= Math.sqrt(x); ++j) {
34            if (x % j === 0) {
35                let count = 0;
36                while (x % j === 0) {
37                    count++;
38                    x /= j;
39                }
40                primeFactors[i].push(count);
41            }
42        }
43        if (x > 1) {
44            primeFactors[i].push(1);
45        }
46    }
47})();
48
49// Compute binomial coefficient using precomputed factorials and their inverses
50const combination = (n: number, k: number): number => {
51    return (((factorial[n] * inverseFactorial[k]) % MOD) * inverseFactorial[n - k]) % MOD;
52};
53
54// Function to calculate ways to fill the array for each query
55const waysToFillArray = (queries: number[][]): number[] => {
56    const answer: number[] = [];
57    for (const query of queries) {
58        const n: number = query[0], k: number = query[1];
59        let totalWays: number = 1;
60
61        // Calculate total number of ways using combinations of prime factors
62        for (const primeFactorCount of primeFactors[k]) {
63            totalWays = (totalWays * combination(primeFactorCount + n - 1, n - 1)) % MOD;
64        }
65        answer.push(totalWays);
66    }
67    return answer;
68};
69
Not Sure What to Study? Take the 2-min Quiz๏ผš

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8
1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12
1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

Time and Space Complexity

Time Complexity:

The time complexity of the code consists of pre-computation and query handling.

Pre-computation:

  • Pre-computation of factorials f[i] and their modular inverses g[i]: This is a linear operation with respect to N, which gives a complexity of O(N).
  • Calculation of prime factors and their exponents for each integer i (up to N): The inner loop has a worst-case square root complexity for prime factorization, which gives O(sqrt(N)) for each i. Since we're doing this for each number up to N, the pre-computation for p has complexity O(N * sqrt(N)).

The overall pre-computation complexity is O(N) + O(N * sqrt(N)), which simplifies to O(N * sqrt(N)), as this is the dominating term.

Query handling:

  • For each query, we must calculate the total number of ways to form arrays. If x is the size of the list of exponents for k, the complexity of computing the product of combinations is O(x). Since x could be at most log(k) (the number of unique prime factors of k), this is O(log(k)).
  • We handle each query in O(log(k)), and if there are Q queries, the overall query handling complexity would be O(Q * log(k)), where k represents the largest number in the queries' second element.

The total time complexity, considering both pre-computation and query handling, is O(N * sqrt(N)) + O(Q * log(k)).

Space Complexity:

The space complexity is driven by the storage requirements for the factorials, modular inverses, and the prime factors list:

  • f[i] and g[i] arrays each consume O(N) space.
  • p, the dictionary of lists, in the worst case, can hold up to log(N) prime factors for each number up to N, which gives us O(N * log(N)).

The overall space complexity is O(N) + O(N) + O(N * log(N)), which simplifies to O(N * log(N)) since this is the dominant term.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Recommended Readings

Math Basics

Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Backtracking 1

Backtracking Template Prereq DFS with States problems dfs_with_states Combinatorial search problems Combinatorial search problems involve finding groupings and assignments of objects that satisfy certain conditions Finding all permutations combinations subsets and solving Sudoku are classic combinatorial problems The time complexity of combinatorial problems often grows rapidly with the size of

Got a question?ย Ask the Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ