Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5. Sample Input : 10 (Value of N) 3 1 2 3 Sample Output : 5
Question
Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter.
For example, for N = 4 and S = {1,2,3}, there are four solutions: {1,1,1,1},{1,1,2},{2,2},{1,3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2,2,2,2,2}, {2,2,3,3}, {2,2,6}, {2,3,5} and {5,5}. So the output should be 5.
Sample Input :
10 (Value of N)
3
1 2 3
Sample Output :
5
Solution
This problem can be solved using dynamic programming. Here are the steps to solve it:
-
Create an array of size N+1 to store the number of ways to make change for all values from 0 to N. Initialize all values as 0 except the first one which should be 1 (since there is exactly one way to make change for 0, which is using no coins).
-
For each coin in the set S, iterate over all values from the coin's value to N. For each value, add the number of ways to make change without the current coin (which is already stored in the array) and the number of ways to make change using at least one of the current coin (which is the number of ways to make change for the current value minus the coin's value).
-
After iterating over all coins, the number of ways to make change for N will be stored in the last position of the array.
Here is a Python code that implements these steps:
def count(S, m, n):
# Create table to store results of subproblems
table = [0 for k in range(n+1)]
# Base case (If given value is 0)
table[0] = 1
# Pick all coins one by one and update the table[] values
# after the index greater than or equal to the value of the
# picked coin
for i in range(0,m):
for j in range(S[i],n+1):
table[j] += table[j-S[i]]
return table[n]
# Driver program to test above function
arr = [1, 2, 3]
m = len(arr)
n = 10
x = count(arr, m, n)
print (x)
In this code, S is the array of coin values, m is the number of different coins, and n is the value for which we want to make change. The function count calculates the number of ways to make change for n using coins of the values given in S. The result is printed at the end.
Similar Questions
Use Dynamic Programming to find the total number of ways you can change the given amount of money (W=5) using given coins(2,3,5).1 point1234Clear selection
ou are given an array of integers ‘coins’ denoting the denomination of coins and another array of integers ‘freq’ denoting the number of coins of each denomination.You have to find the number of ways to make the sum ‘V’ by selecting some(or all) coins from the array.The answer can be very large. So, return the answer modulo 1000000007.For Example :‘N’ = 3, ‘coins’ = {1, 2, 3}, ‘freq’ = {1, 1, 3}, ‘V’ = 6For the given example, we can make six by using the following coins:{1, 2, 3}{3. 3}Hence, the answer is 2.
Consider the problem of creating a particular monetary value using discrete coins, for example: making 15¢ from a 10¢ coin plus a 5¢ coin:denoms = { 1, 5, 10, 25}counts = { 3, 2, 2, 3}result = { 0, 1, 1, 0} // 5 cents + 10 cents = 15 cents For this problem I want to create 29¢ in change, and my cash drawer contains the following coins:denoms = { 1, 5, 10, 25}counts = { 3, 0, 0, 3}result = { 0, 0, 0, 0}(That is: three 1¢ coins and three 25¢ coins are available, but no 5¢ or 10¢ coins at this time, and I have NOT yet begun creating change.)Each step in the change-making process involves taking ONE coin from the counts array and adding it to my result array.Given this setup, which of the following is a valid next step in the process of attempting to make change?Group of answer choicesAdd one 1¢ coin to resultAdd one 5¢ coin to resultAdd one 10¢ coin to resultAdd one 25¢ coin to resultDeclare the 29¢ result impossible
You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.Return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.You may assume that you have an infinite number of each kind of coin. Example 1:Input: coins = [1,2,5], amount = 11Output: 3Explanation: 11 = 5 + 5 + 1Example 2:Input: coins = [2], amount = 3Output: -1Example 3:Input: coins = [1], amount = 0Output: 0 Constraints:1 <= coins.length <= 121 <= coins[i] <= 231 - 10 <= amount <= 104
Write a program that prints the minimum number of coins to make change for an amount of money.Usage: ./change centswhere cents is the amount of cents you need to give backif the number of arguments passed to your program is not exactly 1, print Error, followed by a new line, and return 1you should use atoi to parse the parameter passed to your programIf the number passed as the argument is negative, print 0, followed by a new lineYou can use an unlimited number of coins of values 25, 10, 5, 2, and 1 cent
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.