1735. Count Ways to Make Array With Product
Problem Description
You need to find the number of ways to fill an array with positive integers such that their product equals a given value.
Specifically, you're given multiple queries where each query consists of two values:
n
: the size of the array to fillk
: the target product
For each query [n, k]
, you need to count how many different ways you can place positive integers into an array of size n
such that when you multiply all the integers together, you get exactly k
.
For example, if n = 2
and k = 6
, you could have arrays like:
[1, 6]
(product = 1 × 6 = 6)[2, 3]
(product = 2 × 3 = 6)[3, 2]
(product = 3 × 2 = 6)[6, 1]
(product = 6 × 1 = 6)
So there would be 4 different ways.
Since the number of ways can be very large, each answer should be returned modulo 10^9 + 7
.
The problem requires you to process multiple queries and return an array where each element is the answer to the corresponding query.
The key insight is that this problem can be solved using prime factorization and combinatorial mathematics. When k
is factorized into prime factors k = p₁^x₁ × p₂^x₂ × ... × pₘ^xₘ
, the problem becomes distributing these prime factors across n
positions in the array. This is equivalent to placing xᵢ
identical items (copies of prime pᵢ
) into n
boxes where boxes can be empty, which is a classic combinatorial problem with the solution C(xᵢ + n - 1, n - 1)
for each prime factor.
Intuition
To understand how to solve this problem, let's think about what it means for an array of positive integers to have a product equal to k
.
First, consider the fundamental theorem of arithmetic: every positive integer can be uniquely expressed as a product of prime powers. So if k = 12 = 2² × 3¹
, then any array whose product is 12 must collectively contain exactly two 2's and one 3 among all its elements when we factor them.
This transforms our problem: instead of thinking about distributing arbitrary positive integers into an array, we can think about distributing prime factors. If k = 2² × 3¹
, we need to distribute two 2's and one 3 across n
positions.
For example, with n = 3
and k = 12
:
- We could put both 2's and the 3 in one position:
[12, 1, 1]
- We could separate them:
[4, 3, 1]
(where 4 = 2²) - Or many other combinations:
[2, 2, 3]
,[2, 6, 1]
, etc.
The key insight is that distributing prime factors is independent for each prime. The ways to distribute the 2's doesn't affect how we distribute the 3's. This means we can solve for each prime separately and multiply the results.
Now, how many ways can we distribute x
identical items (copies of a prime) into n
positions? This is a classic "stars and bars" problem in combinatorics. We're essentially asking: how many ways can we write x
as a sum of n
non-negative integers (since some positions can have 0 copies of the prime, meaning that position's number won't contain this prime factor)?
The formula for this is C(x + n - 1, n - 1)
. We can visualize this as arranging x
stars and n - 1
bars, where the bars separate the stars into n
groups. The total number of positions is x + n - 1
, and we choose n - 1
of them for the bars.
Therefore, our solution approach is:
- Factorize
k
into prime powers - For each prime
p
with exponentx
, calculateC(x + n - 1, n - 1)
- Multiply all these combinations together to get the final answer
Learn more about Math, Dynamic Programming and Combinatorics patterns.
Solution Approach
The implementation consists of two main parts: preprocessing and query processing.
Preprocessing Phase:
-
Factorial and Inverse Factorial Arrays: We precompute factorials
f[i] = i!
and their modular inversesg[i] = (i!)^(-1) mod (10^9 + 7)
for all values up toN = 10020
. The inverse is calculated using Fermat's Little Theorem:a^(-1) ≡ a^(MOD-2) (mod MOD)
when MOD is prime. -
Prime Factorization: For each number from 1 to N, we compute its prime factorization and store only the exponents in a dictionary
p
. For example, if12 = 2² × 3¹
, thenp[12] = [2, 1]
. The algorithm uses trial division:- For each number
i
, try dividing by all integersj
from 2 to√i
- Count how many times
j
dividesi
(this gives the exponent) - Store only the exponents, not the primes themselves
- For each number
Combination Calculation:
The function comb(n, k)
calculates C(n, k) = n! / (k! × (n-k)!)
using the precomputed factorials and their inverses:
comb(n, k) = f[n] * g[k] * g[n - k] % MOD
Query Processing:
For each query [n, k]
:
- Retrieve the list of exponents from
p[k]
(the prime factorization of k) - For each exponent
x
, calculate the number of ways to distributex
identical items inton
positions using the formulaC(x + n - 1, n - 1)
- Multiply all these combinations together (taking modulo at each step)
The key insight in the implementation is that we don't need to store which primes correspond to which exponents. Since we're multiplying the combinations for all prime factors, we only need the exponents themselves.
For example, if k = 12 = 2² × 3¹
and n = 3
:
- For the prime 2 with exponent 2: calculate
C(2 + 3 - 1, 3 - 1) = C(4, 2) = 6
- For the prime 3 with exponent 1: calculate
C(1 + 3 - 1, 3 - 1) = C(3, 2) = 3
- Final answer:
6 × 3 = 18
ways
This approach efficiently handles multiple queries by preprocessing all necessary factorizations and using fast combination calculations with precomputed factorials.
Ready to land your dream job?
Unlock your dream job with a 5-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example with n = 3
(array size) and k = 12
(target product).
Step 1: Prime Factorization
First, we factorize k = 12
:
12 = 2² × 3¹
- So we have two 2's and one 3 to distribute across 3 positions
Step 2: Distribute Prime Factor 2 (appears 2 times)
We need to distribute 2 copies of prime 2 across 3 positions. Using the stars and bars formula C(x + n - 1, n - 1)
:
C(2 + 3 - 1, 3 - 1) = C(4, 2) = 6
The 6 ways to distribute two 2's are:
- Position distribution:
[2, 0, 0]
→ Array values:[4, *, *]
- Position distribution:
[1, 1, 0]
→ Array values:[2, 2, *]
- Position distribution:
[1, 0, 1]
→ Array values:[2, *, 2]
- Position distribution:
[0, 2, 0]
→ Array values:[*, 4, *]
- Position distribution:
[0, 1, 1]
→ Array values:[*, 2, 2]
- Position distribution:
[0, 0, 2]
→ Array values:[*, *, 4]
Step 3: Distribute Prime Factor 3 (appears 1 time) We need to distribute 1 copy of prime 3 across 3 positions:
C(1 + 3 - 1, 3 - 1) = C(3, 2) = 3
The 3 ways to distribute one 3 are:
- Position distribution:
[1, 0, 0]
→ Array values:[3, 1, 1]
- Position distribution:
[0, 1, 0]
→ Array values:[1, 3, 1]
- Position distribution:
[0, 0, 1]
→ Array values:[1, 1, 3]
Step 4: Combine Both Distributions
Total ways = 6 × 3 = 18
Some example arrays (combining both prime distributions):
- Two 2's in position 1, one 3 in position 1:
[12, 1, 1]
(12 = 4 × 3) - Two 2's in position 1, one 3 in position 2:
[4, 3, 1]
- One 2 in positions 1 and 2, one 3 in position 3:
[2, 2, 3]
- One 2 in position 1, one 2 in position 3, one 3 in position 2:
[2, 3, 2]
Each valid array will have exactly two factors of 2 and one factor of 3 distributed among its elements, ensuring the product equals 12.
Verification: We can verify a few arrays:
[12, 1, 1]
: product = 12 × 1 × 1 = 12 ✓[2, 2, 3]
: product = 2 × 2 × 3 = 12 ✓[4, 3, 1]
: product = 4 × 3 × 1 = 12 ✓
The final answer is 18 ways to create an array of size 3 with product 12.
Solution Implementation
1from collections import defaultdict
2from typing import List
3
4# Constants
5MAX_VALUE = 10020
6MOD = 10**9 + 7
7
8# Precompute factorials and their modular inverses
9factorials = [1] * MAX_VALUE
10factorial_inverses = [1] * MAX_VALUE
11
12# Precompute prime factorizations
13prime_factorizations = defaultdict(list)
14
15# Initialize factorials, their inverses, and prime factorizations
16for i in range(1, MAX_VALUE):
17 # Compute factorial: i! = (i-1)! * i
18 factorials[i] = factorials[i - 1] * i % MOD
19
20 # Compute modular inverse of factorial using Fermat's Little Theorem
21 # Since MOD is prime, inverse of a is a^(MOD-2) mod MOD
22 factorial_inverses[i] = pow(factorials[i], MOD - 2, MOD)
23
24 # Find prime factorization of i
25 current_number = i
26 divisor = 2
27
28 # Check divisors up to sqrt(current_number)
29 while divisor <= current_number // divisor:
30 if current_number % divisor == 0:
31 # Count the power of this prime factor
32 exponent = 0
33 while current_number % divisor == 0:
34 exponent += 1
35 current_number //= divisor
36 # Store the exponent of this prime factor
37 prime_factorizations[i].append(exponent)
38 divisor += 1
39
40 # If remaining number > 1, it's a prime factor with exponent 1
41 if current_number > 1:
42 prime_factorizations[i].append(1)
43
44
45def combination(n: int, k: int) -> int:
46 """
47 Calculate nCk (n choose k) modulo MOD using precomputed factorials.
48 Formula: nCk = n! / (k! * (n-k)!)
49 """
50 return factorials[n] * factorial_inverses[k] * factorial_inverses[n - k] % MOD
51
52
53class Solution:
54 def waysToFillArray(self, queries: List[List[int]]) -> List[int]:
55 """
56 For each query [n, k], find the number of ways to fill an array of size n
57 with positive integers such that their product equals k.
58
59 Uses the stars and bars method: for each prime factor p^e in k's factorization,
60 we need to distribute e occurrences among n positions, which is C(e+n-1, n-1).
61 """
62 result = []
63
64 for array_size, target_product in queries:
65 ways = 1
66
67 # For each prime factor's exponent in the factorization of target_product
68 for exponent in prime_factorizations[target_product]:
69 # Apply stars and bars: distribute 'exponent' items into 'array_size' bins
70 # This is equivalent to C(exponent + array_size - 1, array_size - 1)
71 ways = ways * combination(exponent + array_size - 1, array_size - 1) % MOD
72
73 result.append(ways)
74
75 return result
76
1class Solution {
2 // Constants for array sizes and modulo arithmetic
3 private static final int MAX_SIZE = 10020;
4 private static final int MODULO = (int) 1e9 + 7;
5
6 // Precomputed factorial values: factorial[i] = i!
7 private static final long[] factorial = new long[MAX_SIZE];
8
9 // Precomputed inverse factorial values: inverseFactorial[i] = (i!)^(-1) mod MODULO
10 private static final long[] inverseFactorial = new long[MAX_SIZE];
11
12 // Prime factorization storage: primeExponents[i] contains the exponents of prime factors of i
13 private static final List<Integer>[] primeExponents = new List[MAX_SIZE];
14
15 // Static initialization block to precompute values
16 static {
17 // Initialize base cases
18 factorial[0] = 1;
19 inverseFactorial[0] = 1;
20
21 // Initialize lists for prime factorization
22 Arrays.setAll(primeExponents, index -> new ArrayList<>());
23
24 // Precompute factorials, inverse factorials, and prime factorizations
25 for (int i = 1; i < MAX_SIZE; ++i) {
26 // Calculate factorial[i] = i * factorial[i-1]
27 factorial[i] = factorial[i - 1] * i % MODULO;
28
29 // Calculate inverse factorial using modular exponentiation
30 inverseFactorial[i] = modularPower(factorial[i], MODULO - 2, MODULO);
31
32 // Find prime factorization of i
33 int number = i;
34
35 // Check for prime factors from 2 to sqrt(number)
36 for (int divisor = 2; divisor <= number / divisor; ++divisor) {
37 if (number % divisor == 0) {
38 int exponent = 0;
39 // Count the exponent of this prime factor
40 while (number % divisor == 0) {
41 ++exponent;
42 number /= divisor;
43 }
44 primeExponents[i].add(exponent);
45 }
46 }
47
48 // If number > 1, it's a prime factor itself with exponent 1
49 if (number > 1) {
50 primeExponents[i].add(1);
51 }
52 }
53 }
54
55 /**
56 * Performs modular exponentiation: (base^exponent) % modulo
57 * Uses binary exponentiation for efficiency
58 */
59 public static long modularPower(long base, long exponent, long modulo) {
60 long result = 1;
61
62 while (exponent != 0) {
63 // If current bit is 1, multiply result by base
64 if ((exponent & 1) == 1) {
65 result = result * base % modulo;
66 }
67 // Square the base for next bit
68 exponent >>= 1;
69 base = base * base % modulo;
70 }
71
72 return result;
73 }
74
75 /**
76 * Calculates binomial coefficient C(n, k) = n! / (k! * (n-k)!)
77 * Uses precomputed factorials and inverse factorials for efficiency
78 */
79 public static long binomialCoefficient(int n, int k) {
80 return (factorial[n] * inverseFactorial[k] % MODULO) * inverseFactorial[n - k] % MODULO;
81 }
82
83 /**
84 * Main method to calculate ways to fill arrays
85 * For each query [n, k], calculates the number of ways to create an array
86 * of length n whose product equals k
87 */
88 public int[] waysToFillArray(int[][] queries) {
89 int queryCount = queries.length;
90 int[] results = new int[queryCount];
91
92 for (int queryIndex = 0; queryIndex < queryCount; ++queryIndex) {
93 int arrayLength = queries[queryIndex][0];
94 int targetProduct = queries[queryIndex][1];
95
96 long totalWays = 1;
97
98 // For each prime factor exponent in the factorization of targetProduct,
99 // calculate the number of ways to distribute it among arrayLength positions
100 // This uses the stars and bars formula: C(exponent + arrayLength - 1, arrayLength - 1)
101 for (int primeExponent : primeExponents[targetProduct]) {
102 totalWays = totalWays * binomialCoefficient(primeExponent + arrayLength - 1, arrayLength - 1) % MODULO;
103 }
104
105 results[queryIndex] = (int) totalWays;
106 }
107
108 return results;
109 }
110}
111
1// Constants for array size and modulo value
2const int MAX_SIZE = 10020;
3const int MOD = 1e9 + 7;
4
5// Precomputed factorials and their modular inverses
6long long factorial[10020];
7long long inverseFactorial[10020];
8
9// Store prime factor exponents for each number
10// primeFactors[i] contains the exponents of prime factors of i
11vector<int> primeFactors[10020];
12
13/**
14 * Fast modular exponentiation
15 * Computes (base^exponent) % modulo using binary exponentiation
16 */
17long long modularPower(long long base, long long exponent, long long modulo) {
18 long long result = 1;
19 while (exponent != 0) {
20 // If current bit is set, multiply result by base
21 if ((exponent & 1) == 1) {
22 result = result * base % modulo;
23 }
24 exponent >>= 1;
25 base = base * base % modulo;
26 }
27 return result;
28}
29
30// Initialize all precomputed values using lambda function
31int initialize = []() {
32 // Compute factorials
33 factorial[0] = 1;
34 inverseFactorial[0] = 1;
35
36 for (int i = 1; i < MAX_SIZE; ++i) {
37 // Calculate i! mod MOD
38 factorial[i] = factorial[i - 1] * i % MOD;
39
40 // Calculate modular inverse of i! using Fermat's Little Theorem
41 // Since MOD is prime, inverse of a is a^(MOD-2) mod MOD
42 inverseFactorial[i] = modularPower(factorial[i], MOD - 2, MOD);
43
44 // Prime factorization of i
45 int num = i;
46
47 // Check all potential prime factors up to sqrt(num)
48 for (int divisor = 2; divisor <= num / divisor; ++divisor) {
49 if (num % divisor == 0) {
50 int exponentCount = 0;
51
52 // Count the exponent of this prime factor
53 while (num % divisor == 0) {
54 ++exponentCount;
55 num /= divisor;
56 }
57
58 // Store the exponent of this prime factor
59 primeFactors[i].push_back(exponentCount);
60 }
61 }
62
63 // If num > 1, it's a prime factor with exponent 1
64 if (num > 1) {
65 primeFactors[i].push_back(1);
66 }
67 }
68 return 0;
69}();
70
71/**
72 * Compute binomial coefficient C(n, k) mod MOD
73 * Uses precomputed factorials and modular inverses
74 */
75int binomialCoefficient(int n, int k) {
76 return (factorial[n] * inverseFactorial[k] % MOD) * inverseFactorial[n - k] % MOD;
77}
78
79class Solution {
80public:
81 /**
82 * For each query [n, k], count ways to fill an array of size n
83 * with positive integers whose product equals k
84 *
85 * The solution uses Stars and Bars theorem:
86 * For each prime factor p^e in k's factorization,
87 * we need to distribute e occurrences among n positions
88 * This equals C(e + n - 1, n - 1)
89 */
90 vector<int> waysToFillArray(vector<vector<int>>& queries) {
91 vector<int> result;
92
93 for (auto& query : queries) {
94 int arraySize = query[0];
95 int targetProduct = query[1];
96
97 long long totalWays = 1;
98
99 // For each prime factor's exponent in targetProduct
100 // Calculate ways to distribute it among arraySize positions
101 for (int primeExponent : primeFactors[targetProduct]) {
102 // Use Stars and Bars: distributing primeExponent items into arraySize bins
103 // This equals C(primeExponent + arraySize - 1, arraySize - 1)
104 totalWays = totalWays * binomialCoefficient(primeExponent + arraySize - 1, arraySize - 1) % MOD;
105 }
106
107 result.push_back(totalWays);
108 }
109
110 return result;
111 }
112};
113
1// Constants for array size and modulo value
2const MAX_SIZE: number = 10020;
3const MOD: number = 1e9 + 7;
4
5// Precomputed factorials and their modular inverses
6const factorial: number[] = new Array(MAX_SIZE);
7const inverseFactorial: number[] = new Array(MAX_SIZE);
8
9// Store prime factor exponents for each number
10// primeFactors[i] contains the exponents of prime factors of i
11const primeFactors: number[][] = Array.from({ length: MAX_SIZE }, () => []);
12
13/**
14 * Fast modular exponentiation
15 * Computes (base^exponent) % modulo using binary exponentiation
16 */
17function modularPower(base: number, exponent: number, modulo: number): number {
18 let result = 1;
19 base = base % modulo;
20
21 while (exponent !== 0) {
22 // If current bit is set, multiply result by base
23 if ((exponent & 1) === 1) {
24 result = (result * base) % modulo;
25 }
26 exponent >>= 1;
27 base = (base * base) % modulo;
28 }
29 return result;
30}
31
32/**
33 * Initialize all precomputed values
34 * Computes factorials, inverse factorials, and prime factorizations
35 */
36function initialize(): void {
37 // Compute factorials
38 factorial[0] = 1;
39 inverseFactorial[0] = 1;
40
41 for (let i = 1; i < MAX_SIZE; i++) {
42 // Calculate i! mod MOD
43 factorial[i] = (factorial[i - 1] * i) % MOD;
44
45 // Calculate modular inverse of i! using Fermat's Little Theorem
46 // Since MOD is prime, inverse of a is a^(MOD-2) mod MOD
47 inverseFactorial[i] = modularPower(factorial[i], MOD - 2, MOD);
48
49 // Prime factorization of i
50 let num = i;
51
52 // Check all potential prime factors up to sqrt(num)
53 for (let divisor = 2; divisor * divisor <= num; divisor++) {
54 if (num % divisor === 0) {
55 let exponentCount = 0;
56
57 // Count the exponent of this prime factor
58 while (num % divisor === 0) {
59 exponentCount++;
60 num = Math.floor(num / divisor);
61 }
62
63 // Store the exponent of this prime factor
64 primeFactors[i].push(exponentCount);
65 }
66 }
67
68 // If num > 1, it's a prime factor with exponent 1
69 if (num > 1) {
70 primeFactors[i].push(1);
71 }
72 }
73}
74
75// Run initialization immediately
76initialize();
77
78/**
79 * Compute binomial coefficient C(n, k) mod MOD
80 * Uses precomputed factorials and modular inverses
81 */
82function binomialCoefficient(n: number, k: number): number {
83 return (((factorial[n] * inverseFactorial[k]) % MOD) * inverseFactorial[n - k]) % MOD;
84}
85
86/**
87 * For each query [n, k], count ways to fill an array of size n
88 * with positive integers whose product equals k
89 *
90 * The solution uses Stars and Bars theorem:
91 * For each prime factor p^e in k's factorization,
92 * we need to distribute e occurrences among n positions
93 * This equals C(e + n - 1, n - 1)
94 */
95function waysToFillArray(queries: number[][]): number[] {
96 const result: number[] = [];
97
98 for (const query of queries) {
99 const arraySize = query[0];
100 const targetProduct = query[1];
101
102 let totalWays = 1;
103
104 // For each prime factor's exponent in targetProduct
105 // Calculate ways to distribute it among arraySize positions
106 for (const primeExponent of primeFactors[targetProduct]) {
107 // Use Stars and Bars: distributing primeExponent items into arraySize bins
108 // This equals C(primeExponent + arraySize - 1, arraySize - 1)
109 const coefficient = binomialCoefficient(primeExponent + arraySize - 1, arraySize - 1);
110 totalWays = (totalWays * coefficient) % MOD;
111 }
112
113 result.push(totalWays);
114 }
115
116 return result;
117}
118
Time and Space Complexity
Time Complexity: O(K × √K + N + m × log K)
The time complexity consists of three main parts:
-
Preprocessing factorials and modular inverses:
O(N)
whereN = 10020
- Computing factorials
f[i]
takesO(N)
time - Computing modular inverses
g[i]
using Fermat's Little Theorem withpow(f[i], MOD - 2, MOD)
takesO(N × log MOD)
, but since MOD is constant, this isO(N)
- Computing factorials
-
Prime factorization for all numbers up to N:
O(N × √N)
- For each number
i
from 1 toN
, we find prime factors - The inner while loop runs up to
√i
times (checkingj <= x // j
is equivalent toj² <= x
) - For each
i
, factorization takesO(√i)
time - Total:
O(N × √N)
which simplifies toO(K × √K)
whereK
represents the maximum value in preprocessing
- For each number
-
Processing queries:
O(m × d)
wherem
is the number of queries andd
is the average number of distinct prime factors- For each query, we iterate through the prime factors of
k
- The number of distinct prime factors of any number ≤ N is
O(log N)
in the worst case - Therefore, this part is
O(m × log K)
- For each query, we iterate through the prime factors of
Space Complexity: O(N)
The space complexity includes:
- Arrays
f
andg
:O(N)
space each - Dictionary
p
storing prime factorizations: In worst case, storesO(N × log N)
total values across all keys, but since we only store exponents (not the primes themselves), and the number of distinct prime factors isO(log N)
, this isO(N × log N)
. However, the dominant term is stillO(N)
from the arrays - The answer list:
O(m)
wherem
is the number of queries
The overall space complexity is O(N)
as the arrays dominate the space usage.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Integer Overflow in Factorial Computation
When computing factorials, the intermediate values grow extremely fast. Even with modular arithmetic, if you forget to apply the modulo operation at each multiplication step, you'll encounter integer overflow.
Pitfall Example:
# Wrong - can cause overflow factorials[i] = factorials[i - 1] * i factorials[i] %= MOD
Solution:
# Correct - apply modulo at each step factorials[i] = factorials[i - 1] * i % MOD
2. Incorrect Modular Inverse Calculation
A critical mistake is using regular division instead of modular multiplicative inverse when calculating combinations. This will produce incorrect results.
Pitfall Example:
# Wrong - regular division doesn't work with modular arithmetic
def combination(n, k):
return factorials[n] // (factorials[k] * factorials[n - k]) % MOD
Solution:
# Correct - use modular multiplicative inverse
def combination(n, k):
return factorials[n] * factorial_inverses[k] * factorial_inverses[n - k] % MOD
3. Missing Edge Cases in Prime Factorization
The most subtle pitfall is forgetting to handle the case where a prime factor larger than √n remains after trial division. This happens when the number itself is prime or has a large prime factor.
Pitfall Example:
# Wrong - misses large prime factors while divisor * divisor <= current_number: if current_number % divisor == 0: exponent = 0 while current_number % divisor == 0: exponent += 1 current_number //= divisor prime_factorizations[i].append(exponent) divisor += 1 # Forgot to check if current_number > 1!
Solution:
# Correct - handle remaining prime factor while divisor * divisor <= current_number: # ... factorization logic ... divisor += 1 # Critical: Check for remaining prime factor if current_number > 1: prime_factorizations[i].append(1)
4. Forgetting Modulo in Product Calculation
When multiplying the combinations for each prime factor, forgetting to apply modulo after each multiplication can lead to overflow.
Pitfall Example:
# Wrong - can overflow ways = 1 for exponent in prime_factorizations[target_product]: ways *= combination(exponent + array_size - 1, array_size - 1) ways %= MOD # Too late!
Solution:
# Correct - apply modulo after each multiplication ways = 1 for exponent in prime_factorizations[target_product]: ways = ways * combination(exponent + array_size - 1, array_size - 1) % MOD
5. Off-by-One Errors in Stars and Bars Formula
The stars and bars formula for distributing n identical items into k distinct boxes is C(n+k-1, k-1). It's easy to mix up the parameters or use the wrong formula variant.
Pitfall Example:
# Wrong formulas that are commonly confused ways *= combination(exponent + array_size, array_size) # Wrong ways *= combination(exponent + array_size - 1, exponent) # Wrong
Solution:
# Correct - C(items + boxes - 1, boxes - 1) ways *= combination(exponent + array_size - 1, array_size - 1)
Which type of traversal does breadth first search do?
Recommended Readings
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
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 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
Want a Structured Path to Master System Design Too? Don’t Miss This!