Leetcode 322: Coin Change [Solution]
Tags: programming, cpp, algorithms, leetcode
Published: 2021-03-11 14:03:26


This question seems to be very easy at first sight and the solution also comes up to mind, but believe me, you are going to guess it wrong if you are not familiar with Dynamic Programming. I also tried the first solution that came up to mind and that was the wrong one. I have mentioned the first and the correct solutions in this article.

**Difficulty:** Medium
**Jump To:**
* [Problem Statement](#problem-statement)
* [Explanation](#explanation)
* [Solution](#solution)
* [Algorithm](#algo)
* [Explanation with an example](#ex-exp)
* [Implementation](#implementation)

---
<a name="problem-statement"></a>
## Problem Statement

**Question:** [https://leetcode.com/problems/coin-change/](https://leetcode.com/problems/coin-change/)


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.

**Example 1:**

> **Input:** coins = [1,2,5], amount = 11
**Output:** 3
**Explanation:** 11 = 5 + 5 + 1

**Example 2:**

> **Input:** coins = [2], amount = 3
**Output:** -1

**Example 3:**

> **Input:** coins = [1], amount = 0
**Output:** 0

**Example 4:**

> **Input:** coins = [1], amount = 1
**Output:** 1

**Example 5:**

> **Input:** coins = [1], amount = 2
**Output:** 2

**Constraints:**

-   `1 <= coins.length <= 12`
-   `1 <= coins[i] <= 231  - 1`
-   `0 <= amount <= 104`

---

## Explanation <a name="explanation"></a>
The problem is simple and relatable, we just need to break an amount into the change based on the coins we have, the special thing is that the number of coins in the change should be minimum i.e. there should not be any combination of coins available which has the number of coins less than your answer.

---

## Solution <a name="solution"></a>

So the first solution that came up in my mind was a greedy approach that I will sort the coins in descending order based on their values and try to include the biggest coin because it will decrease the amount by a bigger value and that can be filled by smaller coins so I'll get the minimum number of coins solution. Like as in Example 1: `coins = [1,2,5], amount = 11` so the sorted coins will be `[5,2,1]` now I'll include `5` first which results in 2 coins, and the rest amount is `11 - (5x2) = 1` which can be fulfilled by `1` coin so I'll be using `3` coins total. The code is below:

```cpp

class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		int ans=0;
		sort(coins.begin(), coins.end(), greater<int>());
		auto ptr = coins.begin();
		while(amount && ptr!=coins.end()){
			if(amount >= (*ptr)){
				ans += (amount/(*ptr));
				amount %= (*ptr);
			}
			ptr++;
		}
		return amount ? -1 : ans;
	}
};
```
BUT
#### BUT
### BUT
This is not a correct solution, Let's look at a beautiful case `coins=[9,6,5,1], amount=11`. If I include `9` then the rest value is `2` which can be created by 2 `1` coins, in this way I'll be using `3 coins` but the correct solution is `2 coins` which can be achieved using 2 coins `5 & 6`.

*So what should be the correct solution???* 

So let's understand the correct solution now. The problem occurred when we included the big element first what if we go for the solution in a subproblem manner? I mean let's try to achieve the solution for `amount=1`, then for `amount=2` then for `amount=3`, and so on until we get the solution for the amount we want. The interesting thing in this is that whenever I'm trying to get the solution for `n`, I already have the solution for all the values below `n` which can be used. 

*Did you ask, how?* So, let's understand that in this way, I will try to include each coin to make a value equals to the current `amount`, If I am able to include this coin then check if including this coin results in the minimum number of coins till now if yes then I'll include this coin else not. Now here this past data will help.  We'll understand this with an example but before that let's see the algorithm first.


### Algorithm: <a name="algo"></a>
1. Create an array `dp` to keep track of all the solution from `0` to `amount`
2. Fill this array with Maximum Value of `Integer`
3. For `amount=0` we need `0` coins so set `dp[0]=0`
4. Now fill the array using the below loop from `i=1` to the `amount`
	1. Try each coin one by one to create  amount `i` using this coin `j`
		1. If the value of this coin is smaller or equal to `i` then do below else pick the next coin
		2. If this coin is included then the rest of the amount is `i-coins[j]`
		3. Now check if a solution exists for this amount i.e. `dp[i-coins[j] != INT_MAX` and including this coins gives better solution then the current one
		4. If yes then include this coin and replace `dp[i]` with new minimum value `dp[i-coins[j] + 1`
5. If `dp[amount]=INT_MAX` i.e there is no solution so return `-1` else return `dp[amount]`


**Time Complexity:**  `O(amount * coins.length)` 
**Space Complexity:** `O(amount)`

---

### Explanation of solution with an example: <a name="ex-exp"></a>

Let's see this with the above example.

> **coins** = [9, 6, 5, 1]
> **amount** = 11

Below is the `dp` array after step-3:

| Dynamic Array | 0   | 1   | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| - | - | - | - | - | - | - | - | - | - | - | - | - |
| dp:  | 0   | INT\_MAX   | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX |

Below is the screenshot of above `dp` array at various stage of the algorithm:

| Dynamic Array | 0   | 1   | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| - | - | - | - | - | - | - | - | - | - | - | - | - |
| i=1  | j=3 | coins\[j\]=1 |   |
| dp:  | 0   | 1   | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX |
| i=2  | j=3 | coins\[j\]=1 |   |
| dp:  | 0   | 1   | 2 | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX |
| i=5  | j=1 | coins\[j\]=5 |   |
| dp:  | 0   | 1   | 2 | 3 | 4 | 1 | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX |
| i=6  | j=1 | coins\[j\]=5 |   |
| dp:  | 0   | 1   | 2 | 3 | 4 | 1 | 2 | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX |
| i=6  | j=2 | coins\[j\]=6 |   |
| dp:  | 0   | 1   | 2 | 3 | 4 | 1 | 1 | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX | INT\_MAX |
| i=11 | j=0 | coins\[j\]=9 |   |
| dp:  | 0   | 1   | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 1 | 2 | 3 |
| i=11 | j=1 | coins\[j\]=5 |   |
| dp:  | 0   | 1   | 2 | 3 | 4 | 1 | 1 | 2 | 3 | 1 | 2 | 2 |


1. **i=1, j=3, coins[j]=1:** `amount=1` can be achieved by using 1 `1` coin so `dp[1]` becomes `1`
2. **i=2, j=3, coins[j]=1:** `amount=2` can be achieved by using 2 `1` coins so `dp[2]` becomes `2`
3. **i=5, j=1, coins[j]=5:** `amount=5` can be achieved by using 5 `1` coins but using 1 `5` coin is better solution as `rest = dp[5 - 5] = 0` so using current coin `5` means we will be using `0+1=1` coin so `dp[5]` becomes `1`
4. **i=6, j=1, coins[j]=5:** `amount=6` can be achieved by using `5` coin as`rest = dp[6 - 5] = 1` so using current coin `5` means we will be using `1+1=2` coin so `dp[6]` becomes `2`
5. **i=6, j=2, coins[j]=6:** `amount=6` can be achieved by using `6` coin and it's a better solution as `rest = dp[6 - 6] = 0` so using current coin `6` means we will be using `0+1=1` coin and it's lesser than current solution `dp[6]=2` so `dp[6]` becomes `1`
6. **i=11, j=0, coins[j]=9:** `amount=9` can be achieved by using coin `9` as `rest = dp[11 - 9] = 2` so using current coin `9` means we will be using `2+1=3` coin so `dp[11]` becomes `3`
7. **i=11, j=1, coins[j]=5:** `amount=11` can be achieved by using coin `5` as well and it's a better solution as `rest = dp[11 - 5] = dp[6] = 1` so using current coin `5` means we will be using `1+1=2` coin and it's lesser than current solution `dp[11]=3` so `dp[11]` becomes `2`

---

## Implementation <a name="implementation"></a>

**C++ Code:**

```cpp
class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {
		// Initialize DP array with INT_MAX and dp[0]=0
		int dp[amount+1];
		dp[0]=0;
		for(int i=1;i<=amount;++i)
			dp[i] = INT_MAX;

		int len = coins.size();

		// Fill DP array from amount=1 to amount's actual value
		for (int i = 1; i <= amount; ++i)
		{
			// Try to include all the coins one by one
			for (int j = 0; j < len; ++j)
			{
				// If this coin is usable(value less than current amount)
				if(coins[j] <= i){
					// What is the cost for rest of the amount
					// If I use this coin
					// eg. if amount=8 and coins[j]=5 then rest is min cost
					// for 8-5 = 3
					int rest = dp[i-coins[j]];
					// If including this coin gives lesser value 
					// than current min value then include it
					if(rest != INT_MAX && rest+1<dp[i]){
						// update min value for amount=i
						dp[i] = rest+1;
					}
				}
			}
		}
		return dp[amount]==INT_MAX ? -1 : dp[amount];
	}
};
```

**Runnable C++ Code:**
{% replit @shivams136/Leetcode-322-Coin-Change-with-minimum-quantity %}

Cover Photo by <a href="https://unsplash.com/@marcschaefer?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Marc Schaefer</a> on <a href="/s/photos/coin-change?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText">Unsplash</a>