3183. The Number of Ways to Make the Sum 🔒

Problem Description

You have an infinite number of coins with values 1, 2, and 6, and only 2 coins with value 4.

Given an integer n, return the number of ways to make the sum of n with the coins you have.

Since the answer may be very large, return it modulo 10^9 + 7.

Note that the order of the coins doesn't matter and [2, 2, 3] is the same as [2, 3, 2].

Intuition

The problem can be approached by using dynamic programming, specifically through the concept of the complete knapsack problem. We start by considering only the coins with values 1, 2, and 6, for which we have an infinite supply.

Define f[j] to be the number of ways to construct the sum j using these coins. Start with the base case f[0] = 1, as there is only one way to make a sum of zero: using no coins at all.

Iterate through the coin values in coins = [1, 2, 6] and, for each coin x, iterate through all possible sums j from x to n, updating f[j] as f[j] = f[j] + f[j - x]. This equation adds the number of ways to form the sum j by using the coin x.

After finding the number of ways to construct n using coins 1, 2, and 6, accommodate the limited supply of the coin with value 4. If n is at least 4, consider the possibility of using one coin of value 4, adding f[n - 4] to the total ways. Similarly, if n is at least 8, consider using both coins of value 4, adding f[n - 8] as well.

Finally, ensure to take results modulo 10^9 + 7 to handle large outputs.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution utilizes the dynamic programming approach aligned with the complete knapsack problem. Here’s a detailed walkthrough of the implementation:

Initialize Variables and Data Structures:
- Set mod to 10^9 + 7 for the modulus operation.
- Define coins as [1, 2, 6], representing the coin types available in infinite supply.
- Initialize a list f of length n + 1 with all elements set to zero. This list will represent the number of ways to make each sum up to n.
- Set the base case f[0] = 1, as there's one way to make the sum zero (using no coins).
Dynamic Programming Transition:
- Iterate over each coin value x in coins.
- For each x, iterate over all sums j from x to n.
- Update f[j] using the formula f[j] = (f[j] + f[j - x]) % mod. This formula considers the number of ways to form the sum j by including the current coin x.
Consider Limited Coins of Value 4:
- After populating f with the ways to make sums using coins 1, 2, and 6, adjust for the actual availability of coins of value 4.
- If the sum n is at least 4, add f[n - 4] to account for sums that can use one coin of value 4: ans = (ans + f[n - 4]) % mod.
- If the sum n is at least 8, add f[n - 8] for the possibility of using two coins of value 4: ans = (ans + f[n - 8]) % mod.
Return the Result:
- Return ans, which holds the final number of ways to form the sum n using the available coins, adjusted for the limited supply of the 4-value coins.

This approach efficiently calculates the number of ways to achieve the desired sum by leveraging dynamic programming to explore all possible combinations of available coins.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate how the solution approach works. Consider the case where n = 7. Our goal is to find the number of ways to make the sum 7 using coins with infinite supply of values 1, 2, and 6, but only 2 coins with value 4.

Step 1: Initialize Variables and Data Structures

We will set mod = 10^9 + 7.
Define coins as [1, 2, 6].
Initialize a list f of length 8 (since n + 1 = 8) with all elements set to zero: f = [0, 0, 0, 0, 0, 0, 0, 0].
Set the base case f[0] = 1: f = [1, 0, 0, 0, 0, 0, 0, 0].

Step 2: Dynamic Programming Transition

For coin 1:
- Update f[j] for j from 1 to 7 using f[j] = (f[j] + f[j - 1]) % mod.
- Result: f = [1, 1, 1, 1, 1, 1, 1, 1].
For coin 2:
- Update f[j] for j from 2 to 7 using f[j] = (f[j] + f[j - 2]) % mod.
- Result: f = [1, 1, 2, 2, 3, 3, 4, 4].
For coin 6:
- Update f[j] for j from 6 to 7 using f[j] = (f[j] + f[j - 6]) % mod.
- Result: f = [1, 1, 2, 2, 3, 3, 5, 5].

Step 3: Consider Limited Coins of Value 4

Our current f indicates the number of ways to form sums using coins with values 1, 2, and 6.
If n (7) is at least 4, consider using one coin of value 4 by adding f[n - 4]:
- f[3] = 2 ways to form 3 using infinite coins; add this to the result: ans = 5 + 2 = 7.
Since n (7) is not at least 8, we do not add f[n - 8] to account for two coins of value 4.

Step 4: Return the Result

We return the final result, which is 7. There are 7 ways to form the sum 7 with the given coins.

This walkthrough demonstrates the dynamic programming approach and consideration for the limited supply of certain coin values.

Solution Implementation

1class Solution:
2    def numberOfWays(self, n: int) -> int:
3        # Define the modulo constant for large numbers
4        MOD = 10**9 + 7
5
6        # List of coin denominations available
7        coins = [1, 2, 6]
8
9        # Initialize a list to hold the ways to make each amount up to n
10        ways = [0] * (n + 1)
11      
12        # Base case: there is one way to make the amount 0, which is to choose no coins
13        ways[0] = 1
14
15        # Iterate over each coin denomination
16        for coin in coins:
17            # For each coin, update the number of ways for each amount from coin to n
18            for amount in range(coin, n + 1):
19                # Update the number of ways to create the current amount
20                ways[amount] = (ways[amount] + ways[amount - coin]) % MOD
21
22        # Initialize the answer to the number of ways to make the amount n
23        result = ways[n]
24
25        # If n is at least 4, add the number of ways to make (n - 4)
26        if n >= 4:
27            result = (result + ways[n - 4]) % MOD
28
29        # If n is at least 8, add the number of ways to make (n - 8)
30        if n >= 8:
31            result = (result + ways[n - 8]) % MOD
32
33        return result
34

1class Solution {
2  
3    /**
4     * Calculates the number of ways to reach a total of n using coins of values 1, 2, and 6.
5     * Additional adjustments are made if n allows for adding scenarios with extra steps of 4 and 8.
6     *
7     * @param n The target number to express with different combinations of coins.
8     * @return The number of ways to reach the target number, modulo 1,000,000,007.
9     */
10    public int numberOfWays(int n) {
11        final int MODULO = (int) 1e9 + 7; // Define the modulo constant
12        int[] coins = {1, 2, 6}; // Array of coin values
13        int[] ways = new int[n + 1]; // Array to track the number of ways to make each total
14        ways[0] = 1; // Base case: only one way to make zero total
15      
16        // Update the ways array by considering each coin
17        for (int coin : coins) {
18            for (int amount = coin; amount <= n; ++amount) {
19                ways[amount] = (ways[amount] + ways[amount - coin]) % MODULO;
20            }
21        }
22      
23        int result = ways[n]; // The base number of ways to reach n
24      
25        // If n is 4 or higher, consider additional ways using extra step 4
26        if (n >= 4) {
27            result = (result + ways[n - 4]) % MODULO;
28        }
29      
30        // If n is 8 or higher, consider additional ways using extra step 8
31        if (n >= 8) {
32            result = (result + ways[n - 8]) % MODULO;
33        }
34      
35        return result; // Return the total number of ways modulo MODULO
36    }
37}
38

1class Solution {
2public:
3    int numberOfWays(int n) {
4        const int MOD = 1e9 + 7; // Define the modulus value for the result
5        int coins[3] = {1, 2, 6}; // The different coins available
6        int dp[n + 1]; // Array to store the number of ways to make each value up to n
7
8        // Initialize the dp array to 0
9        memset(dp, 0, sizeof(dp));
10
11        dp[0] = 1; // Base case: One way to make a sum of 0 (using no coins)
12
13        // Iterate over each coin
14        for (int coin : coins) {
15            // Calculate the number of ways to make each amount from coin to n using the current coin
16            for (int j = coin; j <= n; ++j) {
17                dp[j] = (dp[j] + dp[j - coin]) % MOD;
18            }
19        }
20
21        int result = dp[n]; // The number of ways to make the sum of n using all available coins
22
23        // Additional calculations to handle extra cases based on problem description
24        if (n >= 4) {
25            result = (result + dp[n - 4]) % MOD;
26        }
27        if (n >= 8) {
28            result = (result + dp[n - 8]) % MOD;
29        }
30
31        return result; // Return the total number of ways to make n
32    }
33};
34

1// Function to calculate the number of ways to reach a total of `n` using steps of 1, 2, 6, 4, and 8.
2function numberOfWays(n: number): number {
3    // Define the modulo constant to prevent overflow and ensure results fit within standard numeric limits.
4    const mod = 10 ** 9 + 7;
5  
6    // Create an array to store the number of ways to reach each sum up to `n`.
7    const f: number[] = Array(n + 1).fill(0);
8  
9    // There is one way to achieve a sum of 0: by taking no steps.
10    f[0] = 1;
11  
12    // Consider steps of size 1, 2, and 6 to fill the array with base solutions.
13    for (const step of [1, 2, 6]) {
14        for (let j = step; j <= n; ++j) {
15            // Calculate the number of ways to reach a sum `j` by considering the current step size.
16            f[j] = (f[j] + f[j - step]) % mod;
17        }
18    }
19  
20    // Initialize the answer with the number of ways to reach `n`.
21    let ans = f[n];
22  
23    // If `n` is at least 4, add the ways to reach `n - 4` to consider the additional step size of 4.
24    if (n >= 4) {
25        ans = (ans + f[n - 4]) % mod;
26    }
27  
28    // If `n` is at least 8, add the ways to reach `n - 8` to consider the additional step size of 8.
29    if (n >= 8) {
30        ans = (ans + f[n - 8]) % mod;
31    }
32  
33    // Return the total number of ways to achieve the sum `n`.
34    return ans;
35}
36

Time and Space Complexity

The time complexity of the code is O(n * m), where n is the amount and m is the number of coins. This is because for each coin type, we iterate through the possible amounts from the coin value to n, resulting in an O(n) complexity for each coin. Since there are m coin types, the overall complexity is O(n * m).

The space complexity of the code is O(n), where n is the amount. This is because we utilize a list f of size n + 1 to store the number of ways to make each amount from 0 to n, which results in a linear space usage.

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

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