# Coin Change Problem

#### Minimum Number of Coins Problem

Given a variety of coin types defining a currency system, find the minimum number of coins required to express a given amount of money. Assume infinite supply of coins of every type.

##### Example

Input: Coin types: [1, 3, 5]. Amount to express: 9.

Output: 3

Here are all the unique ways to express 9 as a sum of coins 1, 3 and 5:

1, 1, 1, 1, 1, 1, 1, 1, 1

1, 1, 1, 1, 1, 1, 3

1, 1, 1, 1, 5

1, 1, 1, 3, 3

1, 3, 5

3, 3, 3

Last two ways use the minimal number of coins, 3.

##### Notes:

Every input will include a coin of value 1. This guarantees that a solution will always exist.

There will be no duplicate coin types in the input.

● 1

● 1

● 1

#### Solutions

We've provided two solutions.

#### 1) brute_force_solution.cpp

We will follow the following recursive definition:

If value == 0:

// Zero coins are required to express the value of 0.

// End of recursion. Base case.

return 0

If value > 0:

minimum_coins(value) = min {1 + minimum_coins(value-coins[i])} (where i belongs to [0,n-1] and coins[i]

Basically what we are doing here is exhaustively searching for all the possible combinations of denominations which can generate our desired value and maintain a minimum number of coins required to generate that value and that will be our answer.

This method is not efficient as it computes subproblems again and again.

##### Time Complexity:

O(n^value).

Auxiliary Space Used:

O(value). That’s the maximum number of the recursive calls at a time.

##### Space Complexity:

O(n + value).

Input takes O(n) and the auxiliary space used is O(value).

``````
int minimum_coins(vector &coins, int value) {
// If value is zero return 0.
if (value == 0) {
return 0;
}
// Maximum value assigned initially
int global_min=100005;
for(int i=0; i < coins.size(); i++){
if (coins[i] <= value) {
// To find minimum coins required to make remaining value-coins[i]
int local_min=minimum_coins(coins, value-coins[i]);
// local_min number of coins required to make remaining value-coins[i] and
// 1 coin with value coins[i] used.
if (local_min+1 < global_min) {
global_min=local_min+1;
}
}
}
// Return maintained global minimum value
return global_min;
}
``````

#### 2) optimal_solution.cpp

It is fairly intuitive that the brute force method computes subproblems again and again, so we need to cache the data.

It can be easily done using the bottom-up DP approach. We will use a one-dimensional array as a DP table which at the i-th index stores the minimum number of coins required to value the value i.

Base case: dp=0, other values in the array are set to the positive infinity.

We use 2 loops:

The 1st loop(i) iterates over 1..value.

The 2nd loop(j) iterates over the given coin types.

For every value of i and coins[j] we check if that i (current value to be expressed) is greater than or equals to the coin value, i.e. i>=coins[j]. If yes, then we update dp[i] = min(dp[i],1+dp[i-coins[j]]).

After the dp table has been constructed, dp[value] will

##### Time Complexity:

O(n*value).

The outer loop makes value iterations and the inner one makes n iterations.

Auxiliary Space Used:

O(value).

The size of the dp array.

##### Space Complexity:

O(n + value).

Input takes O(n) and the auxiliary space used is O(value).

``````
const int MAX_VALUE=100005;
int minimum_coins(vector coins, int value) {
// Dp array of size (value+1) and pre filled value MAX_VALUE
vector dp(value+1, MAX_VALUE);
// As number of coins required to make 0 value is 0
dp=0;
// Following nested loop calculates the minimum number of coins
// required to make the value i and stored in dp table
int n=coins.size();
for(int i=1; i <= value; i++) {
for(int j=0; j < n; j++) {
if (i >= coins[j] and 1+dp[i-coins[j]] < dp[i]) {
// Condition that we have found a better minimal solution
dp[i]=1+dp[i-coins[j]];
}
}
}
// Recursive function that calculates the distinct combinations of minimal size
// that has the sum given to the input value
return dp[value];
}
``````

All Posts