The Coin Change Problem
The Coin Change Problem
jppkid + 40 comments watch out for integer overflow :). i had to switch to 64-bit int.
AlphaBeta55 + 2 comments Thank you
abhaykuma + 1 comment long getWays(long n, vector<long> c) {int64_t A[c.size()][n+1]; for(int64_t i=0;i<c.size();i++){A[i][0]=1;} for(int64_t i=0;i<c.size();i++) {for(int64_t j=1;j<=n;j++) { int64_t x,y; x=(i>0) ? A[i-1][j]:0; y=(j-c[i]>=0)? A[i][j-c[i]]:0; A[i][j]=x+y; }} return A[c.size()-1][n];}
what is wrong with this
sxy1573 + 1 comment My method is same to you,l also get wrong . But my debug answer is same to the true answer.
sauravjack + 1 comment same is happening with me.
priyankajiandani + 1 comment same problem I am getting
mohitsnh6 + 1 comment Please add fout << ways; just before closing it in the main function i.e just before fout.close() I don't know why it is not already included.
MT2018016 + 0 comments For Java Users: In the Main function "ways" is not written to the file. Add bufferedWriter.write(String.valueOf(ways)); in the main function.
tashia + 2 comments Thank you !
hargar + 0 comments thanks
kumar_malay888 + 1 comment this is my code and used java8 :- for coin change problem
public static String CoinChange(int input1,int[] input2) { return CoinChange(input1,input2,0,new HashMap()); }
public static String CoinChange(int input1,int[] input2,int a, HashMap<String,Long> memo) { int b = 1; int c = 0; long d = 0; String x = ""; if(input1 == 0) { return (x = String.valueOf(b)); } if(a >= input2.length) { return (x = String.valueOf(c)); } String z = input1+"-"+a; if(memo.containsKey(z)) { d = memo.get(z); return (x = String.valueOf(d)); } int e = 0; long f = 0; while(e <= input1) { int g = input1 - e; f += CoinChange(input2, g, a+1,memo); e += input2[a]; } memo.put(z,f); return(x = String.valueOf(f)); and i was getting a error which is CandidateCode.java:43: error: incompatible types: int[] cannot be converted to int f += CoinChange(input2, g, a+1,memo); can anyone please solve this
iybaron25 + 0 comments The first argument for your method "CoinChange" takes an int. You are passing it "input2" which is an int array.
acodebreaker + 2 comments thanks
Dream_machine + 1 comment thanks :)
hargar + 1 comment thanks
phuadc123 + 1 comment thanks
mohitduklan + 1 comment thanks
naveenkrjr7 + 0 comments thanks :p
amazinghacker + 4 comments Do we have to use recursion with dynamic programming to solve this?
dipu11 + 0 comments [deleted]robbyoconnor + 1 comment dynamic programming is really just caching previous work
oubenal + 1 comment Memoization*
naveenkrjr7 + 0 comments Tabulation
piyusman + 5 comments public static long count(long sum,long[] coins , int coin_num){
if(sum==0){ return 1; } else if(sum<0){ return 0; } else if(coin_num<=0){ return 0; } else if(memo[(int)sum][coin_num]!=-1){ return memo[(int)sum][coin_num]; } else{ memo[(int)sum][coin_num]=count(sum,coins,coin_num-1)+count(sum-coins[coin_num-1],coins,coin_num); return memo[(int)sum][coin_num]; } }
Here we are caching the previous result in memo multidimensional array. First you need to initialize it wih some number(you can use Arrays.fill for that) Also I tried to make it clear what memo is really doing. Means if the ways for particular sum is already there then no need to calulate again. Else go ahead and solve.
sum = amount
coins = array of all available coins.
coin_num is length of coins array(or you can say that next int in first line of this question's input)
So basically if you have
sum = 100;
coins[] = {25,10,5,1};
coin_num = 4;
memo[][] = new long[sum+1][coin_num+1];
and then call countWays(sum,coins,coin_num);
I have a question to others though, in java when I am trying to make it long I have to do a lot of casting, any other way to deal with the 'long' problem.
sushant001 + 1 comment Your comment helped, so here goes mine ... Rather than using 2D array, create another class (Let call it Change having long sum, int coin . override equals and hashcode- hashcode is really important , use hashcode = sum, that will be good enough ).
Now , in place of 2D array, use map (HashMap). and you are done.
Thanks
andadeacu + 0 comments What can store in HashMap? For example: fot the first example: HashMap would contain (1,4), (1,2), (2,1) (2,2) (1,3)
bnegrao + 4 comments I don't understand why if sum == 0 then return 1; If sum is 0 and the coin values are >= 1, how can I have one solution if the sum is 0? if sum is 0 I should have 0 solutions...
qwerjoe + 0 comments if your sum == 0 then you have already found a 'valid' variation of coins in the previous level of the recursion.
And if N = 0, the output should be 1 (zero from every coin type is the 1 and only good solution here)
mk9440 + 0 comments it is just as factorial of zero = 1 ie no of ways.
abhidash + 0 comments Because one valid solution is to not use any coin at all.
dewscoder + 0 comments when sum is zero, a valid selection of coins would be null set i.e., {}, and thats why return 1
jiwan_chung + 2 comments I didn't understand
count(sum,coins,coin_num-1)+count(sum-coins[coin_num-1],coins,coin_num);
part, can anyone explain me kindly? I really want to understand DP... :(
sumeet_ram + 3 comments Its like, what you do for, finding the number of subsets of a set. Whether an element belongs to your set or it doesn't.
Here, either you use the last coin (in your set of given coins) to make change or you dont.
In case you dont use the last (say 'm'th) coin, now you are left with the subproblem of solving the toatal amount('sum' variable here) using onle the remaining 'm-1' coins ([0:m-2] in the array). We cant use the 'm'th coin because by our own assumption, its not part of the subproblem.
In case you use the last coin, you have the subproblem of solving "sum-Value('m'th coin)" using all the 'm' coins ( because using the 'm' th coin once doesnt bar you from using it again).
Finally you can add the count from both the cases as either of them are a possibility in your final solution.
Lemme know if this helped!!
Snigdha_Sanat + 1 comment @sumeet_ram I did not understand it still, can u please elaborate it a bit more? The choice of the 2 subproblems(count(sum,coins,coin_num-1) and count(sum-coins[coin_num-1],coins,coin_num)) do not look intuitive to me- what am I missing?
midnjerry + 4 comments Imagine it like a tree....
let's say we have n = 25 and c = [1,2,3]
we can break it down from 25 into 3 branches by:
25 = 1 + f(24)
25 = 2 + f(23)
25 = 3 + f(22)
each of these scenarios also branch off:
f(24) = 1 + f(23)
f(24) = 2 + f(22)
f(24) = 3 + f(21)
f(23) = 1 + f(22)
f(23) = 2 + f(21)
f(23) = 3 + f(20)
f(22) = 1 + f(21)
f(22) = 2 + f(20)
f(22) = 3 + f(19)
As you keep on propagating... all of the permutations that end up negative are invalid combinations. all of the permutations that end up exactly at 0 are good combinations.
this is a simplistic approach but it's not correct. Because it doesn't differentiate between... [2,2,5] and [5,2,2]. To get only unique combinations you need to remove 1 element from the C set everytime you iterate.
so... it'll look like this (in pseudo code).
static long getWays(long n, long[] c) { if (n < 0) { return 0; } if (n == 0) { return 1; } if (CacheValuePopulated(n)){ return CacheValue(n); } long sum = 0; for (int i = 0; i < c.length; i++) { long target = n - c[i]; long[] subc = subArrayOfCFrom(i to end); long result = getWays(target, subc); if (result > 0) { saveResultToYourCache(result); } sum += result; } return sum; }
Finally... what made the cache problematic was that you can't just save values for any given n. You have to save values for n BASED on the C subArray you used to calculate it.
Since the problem states that all values of c are unique, I used the first element of the c subarray as a key which pointed to its own n+1 array.
So for example, the cache could differentiate between running (5, [1,2,3]) and (5, [2,3])
f(5,[1,2,3]) = 4 (1,1,1,1,1), (1,1,1,2), (1,1,3), (2, 3) f(5,[2,3]) = 1 (2,3)
I hope this helps everyone. I didn't want to give the full answer away. Good luck!
ErikWitkowski + 1 comment but if you remove the element you just use you cannot have repeated elements like [2,2,5], can you?
fzy1995 + 0 comments he didn't remove the element he just used. read again. he's referring to start from i to end, which means it includes the index of the element he just used.
malviyan_shiv + 0 comments Couldn't got how to solve saving to cache problem ?
philip_cori + 0 comments Most helpful comment in this thread.
MinhThai2 + 0 comments I tried using the strategy above but had no sucess due to overlap problem
Then i tried resolving it using knapsack strategy and it worked.
Excel containing the pattern: https://imgur.com/a/qzbDG5S
Solution passed all cases
sasuke29 + 0 comments Thank you so much for your explanation :)
santhos_kumar + 0 comments Greatly helped. Thankyou!
munnusingh + 0 comments While including the current coin as a part of solution why we are recurring it to count(sum-coins[coin_num-1],coins,coin_num). Should not it be count(sum-coins[coin_num],coins,coin_num)? Because, we coin_num is our current coint i.e. mth coin.
munnusingh + 1 comment While including the current coin as a part of solution why we are recurring it to count(sum-coins[coin_num-1],coins,coin_num). Should not it be count(sum-coins[coin_num],coins,coin_num)? Because, we coin_num is our current coint i.e. mth coin.
ljason2020 + 0 comments As I understand it, the variable coin_num begins counting at 1. So coin number 1 would be the first coin in the array, which is actually index 0, hence you must subtract 1 from coin_num. It just depends on how you define the variable. You could use count(sum-coins[coin_num],coins,coin_num), as long as it fits with the rest of your program.
dheerajkr2313 + 0 comments [deleted]
InfinityRedux + 1 comment There is a way of solving this without using recursion at all, just using dynamic programming. Instead of starting with "we want the solution for n" you can instead start with "what can we do with these coins".
ljason2020 + 0 comments Yes, that is correct, but I believe you can do dynamic programming both recursively and iteratively (as you stated). The key aspect of dynamic programming is memoization or tabulation.
ABcdexter19 + 7 comments Did it in python 8-)
Anachor + 8 comments For a moment I was thinking- "What is python 8?"
crazzy7 + 1 comment Me too
agodfrey3 + 1 comment same
agarwal_sumedha1 + 0 comments it is not passing the test case even if the expected value is same as the output
gsnanda + 0 comments [deleted]Coder_BPPIMT + 0 comments Same here
anhthong_381996 + 1 comment it's "8-)" which is a smile face and isn't "python 8".
hargar + 0 comments th@nks {@ is a not at}
srivastava_ambi1 + 0 comments python and then [8-)] -> smiley
Akhil_yadav + 0 comments it's python3
harpz_ + 0 comments lol.. me too :|
amazinghacker + 0 comments [deleted]anhthong_381996 + 0 comments [deleted]frandelarraniaga + 0 comments [deleted]Dularish + 1 comment Can't seem to figure out the problem. It gives correct output on running in my IDE.
#!/bin/python3 import math import os import random import re import sys # Complete the getWays function below. memoizing_dict = {} # Complete the getWays function below. def getWays(n, c): global memoizing_dict if n < 0: return 0 elif n == 0: return 1 elif (n,len(c)) in memoizing_dict.keys(): return memoizing_dict[(n,len(c))] else: cum_sum = 0 for c_index in range(len(c)): c_item = c[c_index] if c_item > n: continue else: result = getWays(n-c_item, c[c_index:]) if result > 0: cum_sum += result memoizing_dict[(n,len(c))] = cum_sum return cum_sum if __name__ == '__main__': fptr = open(os.environ['OUTPUT_PATH'], 'w') nm = input().split() n = int(nm[0]) m = int(nm[1]) c = list(map(int, input().rstrip().split())) # Print the number of ways of making change for 'n' units using coins having the values given by 'c' ways = getWays(n, c) print(ways) fptr.close()
CamJohnson26 + 3 comments The example program is broken, change print(ways) to fptr.write(str(ways))
imdeepmind + 0 comments Thanks man you just saved my life
sauravjack + 1 comment Thanks Bro!!!
lucagiac + 0 comments [deleted]
lucagiac + 0 comments Thank you so much for pointing that out. For Java, I added this line in the main method (right after the call to getWays).
bufferedWriter.write(Long.toString(ways));
shubham10dulkar1 + 2 comments def getWays(n, c):
l=len(c) ways=[[0 for p in range(n+1) ] for m in range(l)] for p in range(0,l): ways[p][0]=1 for p in range(0,n+1,c[0]): #print(p) ways[0][p] = 1 for i in range(1,l): for j in range(1,n+1): p=j-c[i] if p <0: x=0 else: x=ways[i][p] y=ways[i-1][j] ways[i][j]= x+y print(long(ways[l-1][n]))
i m getting expected output still test case not passing
for example
input:
10 4
2 5 3 6
expected output: 5
debug output : 5
still test case fails
plzz help
jamesjosephclar1 + 1 comment I'm getting the same problem with Python 3. Doesn't matter what I try to change the output, nothing works.
Dularish + 2 comments You have to write to file pointer in the main
jamesjosephclar1 + 0 comments Thank you, didn't realise this. Fixed my problem immediately.
7da46svqgw + 0 comments What do you mean? I can't figure out what to do here
prudvhvi + 0 comments plz return dont print
t_newman_uk + 0 comments You, sir, are living in 2088
trancekid + 1 comment thanks :P
amazinghacker + 0 comments [deleted]
subwaymatch + 0 comments Another thanks.
dramforever + 0 comments Can't thank you more...Just got wrong answer for a few test cases and saw your comment
ajcoo + 1 comment what is 64 bit int ? Is it long long ?
ronak319 + 2 comments int64_t ; declare like this . This one is portable and can be used on every machine whether it is 64 or 32 because size of long int and long long int depend on machines also but int64_t guarantee on every machine. In C++;
abhi15kk + 1 comment Thanks a lot.. I used long long int. It gave me WA for 3 cases.. Declaring it your way helped me pass those cases.. I don't know why it is not accepting long long int.
Saras_Arya + 1 comment Was it test case 9, 10, 14. I am getting WA for only those.
abhaykuma + 0 comments resolved ?
jimmyX + 0 comments thanks man, i bought two test cases for that xD
amazinghacker + 0 comments [deleted]tubededentifrice + 0 comments [deleted]quick_dudley + 0 comments That's weird: I was just using 32 bit ints and didn't have any problem.
kohei + 0 comments You saved me!! Thank you!
sonicjoy2002 + 0 comments Damn! Should've read your comment before spending 5 hacko. Thank you.
nitinyadav + 0 comments Thank you
HarryCho + 0 comments Additional info : Overflow occurs on the
answer
. Value ofN
is in the range ofint
(fairly small).maverick55 + 0 comments [deleted]royal146 + 0 comments Thanks
arunwizz + 0 comments thanks .. 3 cases were failing with jave int, java long worked..
suprchan + 0 comments Thank you :-). Failure to handle it costed 3 test cases!
Soumya_cbr + 2 comments Hi, How to switch to 64 bit int in c??? Please help... i am also facing the overflow issue
haha_ha + 0 comments declare long long int datatype instead of declaring int
juan_furattini + 0 comments - C: long long int
- C++: int64_t
Dikaios + 0 comments thanks
ShkKiit + 0 comments Had to buy testcases for that :P Wish i saw your comment haha
guilin + 3 comments the only thing I learn is that alwasy use Long the only thing I learn is that alwasy use Long the only thing I learn is that alwasy use Long --repeat 3 times if it's very oimportant,重要的事情说三遍
skybrown6543 + 3 comments 中国人出现了。。
(盟友),+1s
fengli97 + 0 comments [deleted]rfeng2 + 2 comments 盟友+1
fasalirr + 2 comments love_lion_1 + 0 comments [deleted]wensi + 0 comments 盟友+1
love_lion_1 + 0 comments [deleted]
love_lion_1 + 0 comments 盟友+1
zutianluo + 0 comments 喜相逢…
h493263729 + 0 comments 你好 哈哈
bhanuchand + 0 comments [deleted]shengpu1126 + 0 comments Thank you very much for the tip! This is definitely something that programmers need to take care of: even though the algorithmic logic is right, be mindful of these details in practicality.
AnamikaAna + 0 comments I got all my test cases right after reading this comment :) Thanks a lot
Chuyinzki + 0 comments You are my hero.
hi_kommineni + 0 comments Thanks!!
tomasz_polgrabia + 0 comments I can only add my note: spending one hour on solving the only problem "integer overflow" (my algorithm was fine) without a possibility to look at the test cases makes my face ( ok, I will not embed any gifs, but you can imagine this) MAAAADDDDDDD. Task's author should warn at the beginning that the range of test cases' outputs exceed the normal range of the integer type.
abhinaw + 0 comments Even 64-bit int is not working for two test cases. Though it helped me in one test case.
First three test cases were not getting accepted. After using 64-bit int, two test cases are still not getting accepted.
ajenal + 0 comments Saved my day.
parasgangwani292 + 0 comments thanks
Mumbaikar007 + 0 comments You made my day !!
kumar_malay888 + 1 comment this is my code and used java8 :- for coin change problem
public static String CoinChange(int input1,int[] input2) { return CoinChange(input1,input2,0,new HashMap()); }
public static String CoinChange(int input1,int[] input2,int a, HashMap<String,Long> memo) { int b = 1; int c = 0; long d = 0; String x = ""; if(input1 == 0) { return (x = String.valueOf(b)); } if(a >= input2.length) { return (x = String.valueOf(c)); } String z = input1+"-"+a; if(memo.containsKey(z)) { d = memo.get(z); return (x = String.valueOf(d)); } int e = 0; long f = 0; while(e <= input1) { int g = input1 - e; f += CoinChange(input2, g, a+1,memo); e += input2[a]; } memo.put(z,f); return(x = String.valueOf(f)); and i was getting a error which is CandidateCode.java:43: error: incompatible types: int[] cannot be converted to int f += CoinChange(input2, g, a+1,memo); can anyone please solve this
RA1611003010504 + 0 comments f += CoinChange(input2, g, a+1,memo); You are missing an argument while passing the values here. Your first variable in the function definition is an int type and the second one is an array.
AkankshaRajhans + 1 comment This is my code in Java7 static long getWays(long n, long[] c){ // Complete this function long[] combinations=new long[(int)n]; combinations[0]=1; for(int j=0;j=c[j]) combinations[i]+=combinations[i-(int)c[j]]; } }
return combinations[(int)n];
} I am getting AArrayIndexOutOfBoundsException. Can anyone help ?
gk_2000 + 0 comments you can put code inside 3 backquotes in beginning and end to get formatting
rwan7727 + 3 comments Passed all cases:
int main() { int n; int m; cin >> n >> m; vector <long> c(m); for (int i=0;i<m;i++) cin >> c[i]; vector <long> numways(n+1); // numways[x] means # ways to get sum x numways[0]=1; // init base case n=0 // go thru coins 1-by-1 to build up numways[] dynamically // just need to consider cases where sum j>=c[i] for (int i=0;i<m;i++) { for (int j=c[i];j<=n;j++) { // find numways to get sum j given value c[i] // it consists of those found earlier plus // new ones. // E.g. if c[]=1,2,3... and c[i]=3,j=5, // new ones will now include '3' with // numways[2] = 2, that is: // '3' with '2', '3' with '1'+'1' numways[j]+=numways[j-c[i]]; } } cout << numways[n]; return 0; }
chammika + 0 comments This is the perfect answer ! Hats off!!
jessica_0422 + 0 comments That makes sense, very clear! Thank you!
bishty472 + 0 comments i dont understand what j is.
mugu007 + 0 comments Thank You ... from 3 years in the Future.
mayank7577 + 0 comments why can not I use long long int instead of 64 bit int ?? using long long it is giving debugging output same as desired output but still it is showing wrong answer.
lancerchao + 3 comments A VERY helpful link for anyone who cannot understand the subproblems involved: http://www.ideserve.co.in/learn/coin-change-problem-number-of-ways-to-make-change
anonymouse_pal + 0 comments Thanks! That really helped! :)
ramdev64 + 0 comments Thanks. that was helpful :)
Rav1T3ja + 0 comments Good site for many Important Algorithms. Good contribution lancerchao
mcervera + 3 comments The solution to this problem is a good example of an efficient and tight Dynamic Programming algorithm. For those of you who are struggling with it, here's a tip. The number of ways you can make change for n using only the first m coins can be calculated using:
(1) the number of ways you can make change for n using only the first m-1 coins.
(2) the number of ways you can make change for n-C[m] using the first m coins (where C is the array of coins).
This data allows you to build the recurrence relation.
ricktetstall + 0 comments [deleted]suraj23patel + 1 comment Can anyone please explain how is this recurresnce derived?
mcervera + 1 comment Posting the recurrence would be the same as posting the solution to the problem since it is the only thing that you need to do to solve it.
Hint: define a bidimensional table. Each (m,n) position stores the number of ways you can obtain the amount "n" using only the first "m" coins. Define the boundary conditions and iteratively fill the table. The solution to the problem will be stored in position (M,N).
zxnzysj + 0 comments thanks for your hint
YeahKey + 0 comments Your hint really helped~ Thx
Tsukuyomi1 + 9 comments Keeping it simple :D
n, m = map(int,input().split()) coins = list(map(int,input().split())) dp = [1]+[0]*n for i in range(m): for j in range(coins[i], n+1): dp[j]+=dp[j-coins[i]] print(dp[-1])
multidynamic + 0 comments 👍
sothisislife101 + 1 comment I've seen a lot of solutions similar to this one in other languages, but this is the first one I've seen in python. My solution is much more verbose, and I'm having difficulty understanding what exactly is going on here. Can someone walk me through it?
Tsukuyomi1 + 0 comments dp[j] stores the number of solutions for j. For base case j=0, number of solutions is 1(not using any coin). Now in the for loop, i represents the number of coins you are using. Initially i=0, so you cannot create change for any j>0, hence dp[j]=0 for j>0. Now in each iteration you add a new coin and update the number of solutions for those j which have value not less than the value of ith coin. This update is just adding the number of solutions when we use the ith coin which is equal to the number of solutions of creating change for j-coins[i]. We are finally done when we use all the coins and so we print dp[n].
diego_amicabile + 2 comments Once you get around to understand it, this is a much better and straightforward solution IMHO. It is also more in line with the explanations given on Topcoder.
I would sum up the algorithm this way.
# Initialize an array of combination numbers for all money amounts from 0 until the target amount # For all coin values: # for all money values starting from the coin value up to the target amount: # get the number of combinations for the money value minus the coin value # add this to the number of combinations of the money value, because you can construct them just adding a coin to them
This is a more verbose version with descriptive variables, that allows you to see the algorithm in action:
import sys target_money, coin_count = input().strip().split(' ') target_money, coin_count = [int(target_money), int(coin_count)] coins = list(map(int, input().strip().split(' '))) combinations = [1] + [0] * target_money for coin_index in range(coin_count): print("Combinations before processing coin {}: {}".format(coins[coin_index], combinations), file=sys.stderr) for money in range(coins[coin_index], target_money + 1): if (combinations[money - coins[coin_index]]) > 0: print(" Combinations for {} added to combinations for {} : {} += {}".format(money - coins[coin_index], money, combinations[money], combinations[money - coins[coin_index]]), file=sys.stderr) combinations[money] += combinations[money - coins[coin_index]] print("Combinations after processing coin {}: {}".format(coins[coin_index], combinations), file=sys.stderr) print("Combinations for {} : {}".format(target_money, combinations[target_money]), file=sys.stderr) print(combinations[target_money])
Now for instance, for test case
10 4 2 5 3 6
it will show the process on stderr:
Combinations before processing coin 2: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] Combinations for 0 added to combinations for 2 : 0 += 1 Combinations for 2 added to combinations for 4 : 0 += 1 Combinations for 4 added to combinations for 6 : 0 += 1 Combinations for 6 added to combinations for 8 : 0 += 1 Combinations for 8 added to combinations for 10 : 0 += 1 Combinations after processing coin 2: [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] Combinations before processing coin 5: [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1] Combinations for 0 added to combinations for 5 : 0 += 1 Combinations for 2 added to combinations for 7 : 0 += 1 Combinations for 4 added to combinations for 9 : 0 += 1 Combinations for 5 added to combinations for 10 : 1 += 1 Combinations after processing coin 5: [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2] Combinations before processing coin 3: [1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2] Combinations for 0 added to combinations for 3 : 0 += 1 Combinations for 2 added to combinations for 5 : 1 += 1 Combinations for 3 added to combinations for 6 : 1 += 1 Combinations for 4 added to combinations for 7 : 1 += 1 Combinations for 5 added to combinations for 8 : 1 += 2 Combinations for 6 added to combinations for 9 : 1 += 2 Combinations for 7 added to combinations for 10 : 2 += 2 Combinations after processing coin 3: [1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4] Combinations before processing coin 6: [1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4] Combinations for 0 added to combinations for 6 : 2 += 1 Combinations for 2 added to combinations for 8 : 3 += 1 Combinations for 3 added to combinations for 9 : 3 += 1 Combinations for 4 added to combinations for 10 : 4 += 1 Combinations after processing coin 6: [1, 0, 1, 1, 1, 2, 3, 2, 4, 4, 5] Combinations for 10 : 5
tigerleapgorge + 0 comments This is great. Thank you explaining!
shankarpenore + 0 comments can you please explain the code of processing coin and after prossing :
Combinations for 0 added to combinations for 5 : 0 += 1 Combinations for 2 added to combinations for 7 : 0 += 1 Combinations for 4 added to combinations for 9 : 0 += 1 Combinations for 5 added to combinations for 10 : 1 += 1
can you plz explain these combitions
krozaine + 0 comments You are simply awesome!! Made my day :)
Yu_Zhao1 + 1 comment How could any human beeing possibly come to this solution on his own?
metamemelord + 0 comments It's all practice dude. THis question in specific, is pretty straight forward.
nitishks007 + 0 comments Nice! if we change the order of loop ( i inside j) we will get all possible ways of getting the change. Basically 2,2,5 will counted differently from 2,5,2
wangjiehui11235 + 0 comments Thank you~
shubham10dulkar1 + 1 comment def getWays(n, c):
l=len(c) ways=[[0 for p in range(n+1) ] for m in range(l)] for p in range(0,l): ways[p][0]=1 for p in range(0,n+1,c[0]): #print(p) ways[0][p] = 1 for i in range(1,l): for j in range(1,n+1): p=j-c[i] if p <0: x=0 else: x=ways[i][p] y=ways[i-1][j] ways[i][j]= x+y print(long(ways[l-1][n]))
i m getting expected output still test case not passing
for example
input:
10 4
2 5 3 6
expected output: 5
debug output : 5
still test case fails
plzz help
fqzhou2012 + 0 comments your code is right. However, the website generated codes make you have to add a standard output codes ,like fptr.write(str(ways)) ,before fptr.close(). Besides, your function has to return the output value (ways[l-1][n] rather than printing it (This way the system will regard it as debug)
b_hus_han + 0 comments amazing way to reduce space complexity as well brilliant
kittenintofu + 3 comments For someone new to coding, this is a very interesting question and I def learned quite a lot from it. I'm writing this post just to help myself remember it.
The core concept is:
calculator(coins, numToUse, sum) = calculator(coins, numToUse-1, sum) + calculator(coins, numToUse, sum-coins[numToUse-1]); basically saying for the current sum, it can and only can be achieved by two sub-cases:
(1). you use one less kind of coins, and still achevie this sum.
(2). you still use the same set of coins, but achieve (sum-oneCoinValue). This "oneCoinValue" is the value of the coin that you eliminates in the sub-case (1) And if you total these two cases up, you get what you want.
And the next step is to speed up your program. If you think about it, there are some potential redundent calculations-- for a lot of sub-cases, they ended up trying to calculate the same sum. And here, I made my first improvement, and it FAILED hardcore... i used an array of size sum, as a look up table. Have I calculated the current sum already, if so, don't do the recursive call, but return the value that was already saved in the table; if not do the recursive call, and save the final return value to the lookup table.
Apparently, that approach did NOT end up well. I couldn't even get the first two mini test cases passed. And then I realized, apparently, there are two important arguments that are passed in: sum AND the numToUse, which basically tells you how many types of coins that you are allowed to use to get the sum. So if you only use a one dimentioanl array to save the result, that's not enough. Using coins {1,2,3} to achieve the number 10 of course is not going to be the same as if you only allowed to use coins {1,2}. The lookup table needs to be 2D. And the major calculator function look like this:
private static long calculator(int[] coins, int numToUse, int sum){ if( sum ==0 ){ return 1; } else if(sum < 0 ){ return 0; } else if (numToUse <= 0){ return 0; } else { if (done[sum][numToUse] == -7){ done[sum][numToUse] = calculator(coins, numToUse-1, sum) + calculator(coins, numToUse, sum-coins[numToUse-1]) ; } return done[sum][numToUse]; } } // -7 is just the value that I intialize the array done, I picked it becuase I like number 7, haha
svadali2 + 0 comments thank you for that, even though you wrote it for yourself :)
stanfordkansas + 1 comment With yr impelemetation:
-Time Complexity is O(2^m) because of all possible subsets of the given coins
-Space Complexity is O(nm)
Is it right?
aitrop + 1 comment Seems like an overly complicated recursive solution to me. Surprised if it passed runtime tests.
pendell + 0 comments Others have downvoted the comment, and the reason why is that it is essentally the same solution as in the editorial. There are some additional test cases that the editorial doesn't have, but the logic is otherwise sound.
The reason it passes the runtime tests is because of the if (done[sum][numToUse] == -7) check. This ensures that we only compute solutions one time -- if we need the same solution again, we just use the previously computed solution.
ammar_lokh1234 + 1 comment Hey I have a javascript program done the same way as OP, however I'm getting a runtime time error with my "done" array. I'm new to JS so can somebody help me spot the issue?
function getWays(n, c, m, done){ // Complete this functionc var res=0; if(n==0) { return 1; } if(n<0) return 0; if(m<=0) return 0; else { // Here is where I get the error: TypeError: Cannot read property '2' of undefined if(done[n][m]==-1) done[n][m] = getWays(n-c[m-1],c,m, done) + getWays(n,c,m-1, done); return done[n][m]; } } function main() { var n_temp = readLine().split(' '); var n = parseInt(n_temp[0]); var m = parseInt(n_temp[1]); var done = []; c = readLine().split(' '); c = c.map(Number); for(var i=0;i<n;i++){ var col = []; for(var j=0;j<m;j++) { col[j] =-1; } done[i] = col; } // Print the number of ways of making change for 'n' units using coins having the values given by 'c' var ways = getWays(n, c, m-1, done); console.log(ways); }
schrecka + 0 comments I have the same problem did you figure this out
ishtiaque_h + 1 comment There's a very good explanation from Gayle (author of Cracking the Coding Interview book) for this problem in YouTube. Watch: https://www.youtube.com/watch?v=sn0DWI-JdNA
gravitation + 0 comments Thanks
Nothing in this thread really helped me at all, but after watching one minute of this video I realized the error in my approach to the problem
nelson_a_antunes + 3 comments DP in python2 with 1D list/array:
value,_ = map(int,raw_input().strip().split(' ')) coins = map(int,raw_input().strip().split(' ')) ways = [0]*(value+1) for coin in coins: if coin > value: #if coin > value, there's no reason to use it continue ways[coin]+=1 #coin by itself as a set for i in range(coin+1,value+1): #fill the remaining sets with a new possibility with this coin ways[i] += ways[i-coin] print ways[value]
rswaghmare + 0 comments Wow! Did you develop this algorithm yourself?
katsmanva + 0 comments I was thinking about implementation for 2 todays, man, brilliant solution!
isharth + 0 comments genius
pujakuntal123 + 3 comments Ridiculous .. all answer come correct but compiler throwing message ..wrong answer
logesssh + 2 comments add this line to main class
bufferedWriter.write(String.valueOf(ways)); bufferedWriter.newLine();
JaySingh566 + 0 comments Thanks man!
anil09 + 0 comments In C, i faced the same problem. You should print the message in file. I used fprintf instead of printf. And the problem got resolved.
dnavalta + 0 comments I think the solution by logesssh is in java, but I don't know for sure. In python, the answer is to have your function return the value, then after the function call in main use
fptr.write(str(ways))
akshaykabra + 3 comments the input format of the question is not clear/really_bad. Also no constraints are given.
PRASHANTB1984 + 2 comments That section got wiped out along with some other changes. We'll be restoring it in a while.
roshan_santhosh + 1 comment Its been 9 days already. When will t be changed? The format is very unclear.
PRASHANTB1984 + 2 comments just updated it. Can you refresh?
akshaykabra + 0 comments Sir if number of coins to be taken would have been in input format it would be easier to take input.. can you please update the format??
JaskaranSingh + 1 comment What is the bound on M-the number of coins?
The input format isn't good.Right now the problem looks more of a challenge of input parsing rather than DP.
akshaykabra + 0 comments :D :D :D agree !! :)
amazinghacker + 1 comment [deleted]quick_dudley + 0 comments No, it's not necessary: I just used 2 loops.
amazinghacker + 0 comments [deleted]bossgates + 0 comments - Use long instead of int
- In some cases, Ci > N
CamJohnson26 + 0 comments The Python 3 template is broken. After the call to
getWays
should be this line:fptr.write(str(ways))
Sort 391 Discussions, By:
Please Login in order to post a comment