Facebook Pixel

1735. Count Ways to Make Array With Product

HardArrayMathDynamic ProgrammingCombinatoricsNumber Theory
Leetcode Link

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 fill
  • k: 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.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. Factorize k into prime powers
  2. For each prime p with exponent x, calculate C(x + n - 1, n - 1)
  3. 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:

  1. Factorial and Inverse Factorial Arrays: We precompute factorials f[i] = i! and their modular inverses g[i] = (i!)^(-1) mod (10^9 + 7) for all values up to N = 10020. The inverse is calculated using Fermat's Little Theorem: a^(-1) ≡ a^(MOD-2) (mod MOD) when MOD is prime.

  2. 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, if 12 = 2² × 3¹, then p[12] = [2, 1]. The algorithm uses trial division:

    • For each number i, try dividing by all integers j from 2 to √i
    • Count how many times j divides i (this gives the exponent)
    • Store only the exponents, not the primes themselves

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]:

  1. Retrieve the list of exponents from p[k] (the prime factorization of k)
  2. For each exponent x, calculate the number of ways to distribute x identical items into n positions using the formula C(x + n - 1, n - 1)
  3. 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 Evaluator

Example 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:

  1. Preprocessing factorials and modular inverses: O(N) where N = 10020

    • Computing factorials f[i] takes O(N) time
    • Computing modular inverses g[i] using Fermat's Little Theorem with pow(f[i], MOD - 2, MOD) takes O(N × log MOD), but since MOD is constant, this is O(N)

  2. Prime factorization for all numbers up to N: O(N × √N)

    • For each number i from 1 to N, we find prime factors
    • The inner while loop runs up to √i times (checking j <= x // j is equivalent to j² <= x)
    • For each i, factorization takes O(√i) time
    • Total: O(N × √N) which simplifies to O(K × √K) where K represents the maximum value in preprocessing

  3. Processing queries: O(m × d) where m is the number of queries and d 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)

Space Complexity: O(N)

The space complexity includes:

  • Arrays f and g: O(N) space each
  • Dictionary p storing prime factorizations: In worst case, stores O(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 is O(log N), this is O(N × log N). However, the dominant term is still O(N) from the arrays
  • The answer list: O(m) where m 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)
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

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

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More