We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The Number of Ways to Make the Sum

Number: 3489

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an integer n, determine the number of combinations to form the sum n using an infinite number of coins with values 1, 2, and 6, along with only 2 coins available with a value of 4. Note that the order in which the coins are selected does not create a distinct combination.

Key Insights

  • The unlimited coins (1, 2, 6) allow the use of the classic coin change dynamic programming (DP) approach.
  • The value 4 coin is limited (only 2 available), so we must consider separately the cases where 0, 1, or 2 coins of value 4 are used.
  • For every option of using 0 to 2 coins of value 4, we compute the remaining sum to be formed using the unlimited coins.
  • Sum the valid ways modulo 10^9+7.

Space and Time Complexity

Time Complexity: O(n) – We compute a DP array of size n for the unlimited coins. Space Complexity: O(n) – We use an additional DP array to store the number of ways for each amount up to n.

Solution

We first compute a DP array (dpInf) which counts the number of ways to form every sum from 0 to n using the infinite coins (1, 2, 6). This is done using the standard coin change approach: for each coin, iterate through all sums from the coin’s value up to n and update dpInf.

After filling dpInf, we consider the limited coin (4), which can be used 0, 1, or 2 times. For each possibility, subtract the total contribution of coin 4 (i.e. count4 * 4) from n, and add dpInf[remaining] to the result if the remaining sum is non-negative. Finally, we return the answer modulo 10^9+7.

Code Solutions

MOD = 10**9 + 7

def ways_to_make_sum(n):
    # dpInf[i] will store the number of ways to form the sum i using coin values [1,2,6]
    dpInf = [0] * (n + 1)
    dpInf[0] = 1  # Base case: one way to make 0 sum

    # list of coins that are unlimited
    unlimited_coins = [1, 2, 6]
    
    # Classic coin change DP for unlimited coins
    for coin in unlimited_coins:
        for amount in range(coin, n + 1):
            dpInf[amount] = (dpInf[amount] + dpInf[amount - coin]) % MOD

    total_ways = 0
    # Check for each possibility of using coin of value 4 (0, 1, or 2 times)
    for count_four in range(0, 3):  # 0, 1, and 2 coins of value 4
        remaining = n - count_four * 4
        if remaining >= 0:
            total_ways = (total_ways + dpInf[remaining]) % MOD

    return total_ways

# Example usage:
print(ways_to_make_sum(4))  # expected output: 4
print(ways_to_make_sum(12)) # expected output: 22
print(ways_to_make_sum(5))  # expected output: 4
← Back to All Questions