Hope you are doing well and keeping safe! Last evening my wife and I, after stopping a movie we were watching on Netflix, went to bed. It was still snowing on and off. We were both very tired. Today when we were having breakfast, we noticed that the driveway and path to our door had been cleared of snow. We did not hear a thing. That confirms we were really tired last evening.
One of my best friends (have two sent me the link to the article “Top Universities Took Billions in Unreported Foreign Funds, U.S. Finds”, by the Wall Street Journal. The article is quite interesting. It shows how China is
gifting money (there are no free lunches) to top USA learning institutions (mostly Ivy League universities) in order to take / steal intellectual property, allowing China to avoid developing technologies at much higher costs. This was discovered due to the fact that those same institutions have been forgetting to pay the associated gift / donation taxes. Shame on you Cornell University!
On a much lighter note, earlier this morning I read the article “No Time To Die: 10 Spy Thrillers To Watch Before The New Bond Movie Is Released” by Sam Hutchinson. I am a James Bond fan. In the past decade or so my wife and 
I, on opening day, have been getting cinema tickets after work for all the new 007 movies. This year due to the COVID-19 pandemic, the opening date for “No Time To Die” has been postponed to 2021. Hopefully we will be at a theater on opening night next year.
Our oldest son read the same article and sent us a message with the link. The article contains a set of ten movies to watch in order to alleviate the wait for the release of the new Bond flick. It seems that my wife and I have watched most of the suggested movies. Will review the list in more detail this evening and hopefully will be able to watch the ones we have missed in the next few days.
The main topic for this post is LeetCode problem 322 Coin Change. As I was starting to generate this post, I noticed a document with a similar name. I went to my blog and found the post Coin Change 2 from March 02, 2017. Once again, the code in the post is mangled and to top it off, I did not post it to GitHub. If I have some time I will correct both items in the near future. Sorry about that.
You are given coins of different denominations and a total amount of money amount. Write a function to compute 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. Constraints: 1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104
The requirements for this problem are quite simple to understand. You have to put together the specified amount using an unlimited amount of coins from the specified denominations. This happens when the cashier at a store is giving you back change for a purchase. Just thinking about it, most people now a day pay with their phone or credit card and many checking out points do not have a cashier. Some places are using advance software so you can just pick out what you need, place it in your cart, and walk out without stopping by a checking out point. All is done with software, cameras and sensors throughout the store.
public int coinChange(int[] coins, int amount) {
}
We need to populate the coinChange() function which provided the coin denominations and amount, should return the minimum number of coins needed for the specified amount.
1,2,5 11 main <<< coins: [1, 2, 5] main <<< amount: 11 main <<< coinChange: 3 2 3 main <<< coins: [2] main <<< amount: 3 main <<< coinChange: -1 1 0 main <<< coins: [1] main <<< amount: 0 main <<< coinChange: 0 1 1 main <<< coins: [1] main <<< amount: 1 main <<< coinChange: 1 1,2,5,10 24 main <<< coins: [1, 2, 5, 10] main <<< amount: 24 main <<< coinChange: 4 1,2,5,10 23 main <<< coins: [1, 2, 5, 10] main <<< amount: 23 main <<< coinChange: 4 3,5,10 24 main <<< coins: [3, 5, 10] main <<< amount: 24 <<< dp: [0, 25, 25, 1, 25, 1, 2, 25, 2, 3, 1, 3, 4, 2, 4, 2, 3, 5, 3, 4, 2, 4, 5, 3, 5] main <<< coinChange: 5 1,2,3,5,7,11,13,17,19,23 10 main <<< coins: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23] main <<< amount: 10 <<< dp: [0, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2] main <<< coinChange: 2 1,2,3,5,7,11,13,17,19,23,29 30 main <<< coins: [1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29] main <<< amount: 30 <<< dp: [0, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31] <<< dp: [0, 1, 1, 1, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 1, 2, 2, 2, 1, 2, 2, 2, 3, 2, 1, 2] main <<< coinChange: 2 1,2,3 6 main <<< coins: [1, 2, 3] main <<< amount: 6 <<< dp: [0, 7, 7, 7, 7, 7, 7] <<< dp: [0, 1, 1, 1, 2, 2, 2] main <<< coinChange: 2 1,2,3 5 main <<< coins: [1, 2, 3] main <<< amount: 5 <<< dp: [0, 1, 1, 1, 2, 2] main <<< coinChange: 2 2,3,5,10 15 main <<< coins: [2, 3, 5, 10] main <<< amount: 15 <<< dp: [0, 16, 1, 1, 2, 1, 2, 2, 2, 3, 1, 3, 2, 2, 3, 2] main <<< coinChange: 2 1,5,6,9 11 main <<< coins: [1, 5, 6, 9] main <<< amount: 11 <<< dp: [0, 1, 2, 3, 4, 1, 1, 2, 3, 1, 2, 2] main <<< coinChange: 2 4,10,25 41 main <<< coins: [4, 10, 25] main <<< amount: 41 <<< dp: [0, 42, 42, 42, 1, 42, 42, 42, 2, 42, 1, 42, 3, 42, 2, 42, 4, 42, 3, 42, 2, 42, 4, 42, 3, 1, 5, 42, 4, 2, 3, 42, 5, 3, 4, 2, 6, 4, 5, 3, 4, 5] main <<< coinChange: 5 1,5,6,9 10 main <<< coins: [1, 5, 6, 9] main <<< amount: 10 <<< dp: [0, 1, 2, 3, 4, 1, 1, 2, 3, 1, 2] main <<< coinChange: 2
LeetCode provides some test cases. I also added some while reading, watching videos and experimenting with code. Like I always say, you need to experiment to learn.
The test scaffolding that I generated reads the coin denominations from the 
first line. From the second line it reads the amount. Both pieces of data are displayed in order to verify all is well ingesting the data. Some extra information is displayed while generating the answer. The answer is displayed in the last line of each example.
We will use dynamic programming to tackle the problem. I decided to use the Java programming language. I used the VSCode IDE which in this case exhibited a strange behavior that I did not like. I developed the code on a Windows 10 machine. Of course the platform and IDE should make no difference.
/**
* Test scaffolding
*/
public static void main(String[] args) {
// **** open scanner ****
Scanner sc = new Scanner(System.in);
// **** read the coin denominations ****
String[] denominations = sc.nextLine().trim().split(",");
// **** read the amount ****
int amount = Integer.parseInt(sc.nextLine().trim());
// **** close scanner ****
sc.close();
// *** convert denomination string to integer ****
int coins[] = new int[denominations.length];
for (int i = 0; i < coins.length; i++)
coins[i] = Integer.parseInt(denominations[i]);
// **** display the parameters for the function ****
System.out.println("main <<< coins: " + Arrays.toString(coins));
System.out.println("main <<< amount: " + amount);
// **** process the data and display results ****
System.out.println("main <<< coinChange: " + coinChange(coins, amount));
}
The test scaffolding is a simple as possible. We open the scanner, read the data, and then close the scanner since we are done using it. The coin denominations are used to load the coins array and the data is displayed. We then call the function that should generate the answer and display the returned value.
main <<< amount: 6
<<< dp: [0, 7, 7, 7, 7, 7, 7]
<<< (0,0)
<<< (0,1)
<<< (0,2)
<<< (1,0)
<<< min(7,1)
<<< min: 1
<<< (1,1)
<<< (1,2)
<<< (2,0)
<<< min(7,2)
<<< min: 2
<<< (2,1)
<<< min(2,1)
<<< min: 1
<<< (2,2)
<<< (3,0)
<<< min(7,2)
<<< min: 2
<<< (3,1)
<<< min(2,2)
<<< min: 2
<<< (3,2)
<<< min(2,1)
<<< min: 1
<<< (4,0)
<<< min(7,2)
<<< min: 2
<<< (4,1)
<<< min(2,2)
<<< min: 2
<<< (4,2)
<<< min(2,2)
<<< min: 2
<<< (5,0)
<<< min(7,3)
<<< min: 3
<<< (5,1)
<<< min(3,2)
<<< min: 2
<<< (5,2)
<<< min(2,2)
<<< min: 2
<<< (6,0)
<<< min(7,3)
<<< min: 3
<<< (6,1)
<<< min(3,3)
<<< min: 3
<<< (6,2)
<<< min(3,2)
<<< min: 2
<<< dp: [0, 1, 1, 1, 2, 2, 2]
main <<< coinChange: 2
As you will see shortly in the code for the coinChange() function, I have left several messages that display information which should help us understand what is going on. In this case, we are given three coin denominations: 1, 2, 3 and we need to return an amount of 6 using the minimum number of coins. This example is simple to understand and relatively short to compute. It seems that the logical answer should be 2 coins because 3 + 3 = 6.
For memoization we will use the dp (for dynamic programming) array. We will initialize it as illustrated in the screen capture. The first entry is to used and set to 0. The rest of the entries are set to: amount + 1. The result should will be placed the last entry of the dp array after all the processing is done.
After all is said and done, we display the contents of the dp array. Note that the last entry dp[6] contains the answer for this example.
/**
* You are given coins of different denominations and a total amount of money amount.
* Write a function to compute 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.
*
* Dynamic programming question.
* Bottom up approach.
*
* Runtime: 11 ms, faster than 88.15% of Java online submissions.
* Memory Usage: 38.2 MB, less than 6.61% of Java online submissions.
*/
static int coinChange(int[] coins, int amount) {
// **** sanity check(s) ****
if (amount == 0)
return 0;
// **** sort coins in ascending order ****
Arrays.sort(coins);
// **** initialization ****
int max = amount + 1;
int[] dp = new int[max];
Arrays.fill(dp, 1, max, max);
// ???? ????
System.out.println("<<< dp: " + Arrays.toString(dp));
// **** loop for all amounts until we reach the desired one ****
for (int a = 0; a <= amount; a++) {
// **** iterate through all the coins ****
for (int c = 0; c < coins.length; c++) {
// ???? ????
System.out.println("<<< (" + a + "," + c + ")");
// **** ****
if (coins <= a) {
// ???? ????
System.out.println("<<< min(" + dp[a] + "," + (1 + dp[a - coins]) + ")");
// **** min of ****
int m = Math.min(dp[a], 1 + dp[a - coins]);
// ???? ????
System.out.println("<<< min: " + m);
// **** ****
dp[a] = m;
} else {
// ???? ????
// System.out.println("<<< coins[" + c + "]: " + coins + " > a: " + a);
// **** get to the next larger denomination coin ****
// break;
}
}
}
// ???? ????
System.out.println("<<< dp: " + Arrays.toString(dp));
// **** return result ****
return dp[amount] > amount ? -1 : dp[amount];
}
We start by performing some sanity checks. The problem does not state that the coins are in monotonically ascending order, so we sort the coins.
We then perform some initialization operations to create and initialize the dp array. The array is then displayed to make sure all is ready for processing.
We encounter two loops. The outer loop iterates on all the amount values. The inner loop iterates through all the coins. The idea is to determine the minimum number of coins needed per amount.
We start with the dp array populated with [0, 7, 7, 7, 7, 7, 7]. On each pass we check the condition and if true we update the contents of the dp array. When all is said and done the value in dp[6] contains the result, which in this example is 2 coins.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, or if you would like for me to help out with any phase in the SDLC (Software Development Life Cycle) of a project associated with a product or service, please do not hesitate and leave me a note below. If you prefer, send me a private e-mail message. I will reply as soon as possible.
Keep on reading and experimenting. It is the best way to learn, become proficient, refresh your knowledge and enhance your developer toolset!
One last thing, many thanks to all 3356 subscribers to this blog!!! I really appreciate it.
Keep safe during the COVID-19 pandemic and help restart the world economy.
John
E-mail: john.canessa@gmail.com