We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
The Coin Change Problem
You are viewing a single comment's thread. Return to all 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: