Problem: Please implement a function which gets the minimal number of coins, whose value is v_{1}, v_{2}, …, v_{n}, to make change for an amount of money with value t. Any coin with value v_{i} may duplicate for any times to make change.
For example, the minimal number of coins to make change for 15 out of a set of coins with value 1, 3, 9, 10 is 3. We can choose two coins with value 3 and a coin with value 9. The number of coins for other choices should be greater than 3.
Analysis: Firstly let us define a function f(t) which is the minimal number of coins to make change for total value t. If there are n different coins, we have n choices to make change for value t: we can add a coin with value v_{1} into a set of coins whose total value is tv_{1}. The minimal number of coins to get value tv_{1} is f(tv_{1}). Similarly, we can add a coin with value v_{2} into a set of coins whose total value is tv_{2}. The minimal number of coins to get value tv_{2} is f(tv_{2})…
Therefore, we divide a problem to calculate f(t) into n subproblems: f(tv_{1}), f(tv_{2}), …, f(tv_{n}). We can get a formal equation for f(t) as the following accordingly:
This equation can be implemented with recursion easily. However, the recursive solution will cause serious performance issues since there are overlaps when we divide this problem into n subproblems. A better solution is to utilize iteration, and store the result of subproblems into a table (as the Table 1).
In the Table 1, each column except the first one is to denote the number of coins to make change for a specific value. We can calculate the numbers in the Table 1 from left to right, to simulate the iterative process to get the result of f(15).
For instance, there are two numbers 4 and 2 under the column title “6”. We have two alternatives to make change for 6: the first one is to add a coin with value 1 to a set of coins whose total value is 5. Since the minimal number of coins to get value 5 is 3 (highlighted number under the column tile “5”), the number in the first cell under column title “6” is 4 (4=3+1). The second choice is to add a coin with value 3 to a set of coins whose total value is 3. Since the minimal number of coins to get value 3 is 1 (highlighted number under the column tile “3”), the number in the second cell under column title “6” is 2 (2=1+1). We highlight the number 2 in the column under tile 6 because 2 is less than 4.
0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15
 
1

0

1

2

3

2

3

4

3

4

5

2

2

3

3

4

5

3

0





1

2

3

2

3

4

3

4

5

2

2

3

3

9

0

















1

2

3

2

3

4

3

10

0



















1

2

3

2

3

4

Table 1: The iterative process to calculate the minimal number of coins to make changes for 15.
Even though we have a 2D matrix to show the iterative process, it only requires a 1D array for coding, because it is only necessary to store the minimal number of coins to make change for each total value. The sample code is shown below:
int GetMinCount(int total, int* coins, int length)
{
int* counts = new int[total + 1];
counts[0] = 0;
const int MAX = 0x7FFFFFFF;
for(int i = 1; i <= total; ++ i)
{
int count = MAX;
for(int j = 0; j < length; ++ j)
{
if(i  coins[j] >= 0 && count > counts[i  coins[j]])
count = counts[i  coins[j]];
}
if(count < MAX)
counts[i] = count + 1;
else
counts[i] = MAX;
}
int minCount = counts[total];
delete[] counts;
return minCount;
}The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact me (zhedahht@gmail.com) . Thanks.
I do have a question> Shouldn't be more efficient a simple while(currentSum>0) and then going from the largest denomination to the smallest till currentSum becomes Zero ??
ReplyDeleteYou are indicating greedy approach, it does not produce optimal result in every case.
Deletebaobao autodesk
ReplyDeleteHello Buddy,
ReplyDeleteGreat piece on #topic, I’m a fan of the ‘flowery’ style Looking forward to more long form articles ??
Is there any way we can contact anyone from AWS support since this has become an urgent issue for us, and may potentially be a security concern based on our investigation. We'll be glad to get on the phone to sort this out further.
Anyways great write up, your efforts are much appreciated.
Kind Regards,
Hey There,
ReplyDeleteSuch vivid info on the Interview Puzzles! Flabbergasted! Thank you for making the read a smooth sail!
I have just received an email that says, ""We're writing to provide you with an electronic invoice for your use of AWS services for the billing period April 1  April 30, 2018. Additional information regarding your bill, individual service charge details, and your account history are available on the Billing & Cost Management Page.""
I started using this AWS Tutorial blog for my training practice.
Thanks a lot. This was a perfect stepbystep guide. Don’t think it could have been done better.
Thank you,
Morgan
Salemetsiz Be,
ReplyDeleteGrazie! Grazie! Grazie! Your blog is indeed quite interesting around No. 26  Minimal Number of Coins for Change. I agree with you on lot of points! AWS Training USA
Since yesterday my EC2 instance in Singapore has become inaccessible to some US customers. Does anyone else have similar problems?
Please keep providing such valuable information.
Cheers,
Radhey