Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

coin
change
problem
memoization

Coin change problem 1 in Java:Finding the minimum number of coins

Educative Answers Team

The coin-change problem resembles the 0-1 Knapsack Problem in Dynamic Programming. It has two versions:

  1. Finding the minimum number of coins, of certain denominations, required to make a given sum.
  2. Finding the total number of possible ways a given sum can be made from a given set of coins.

Below is the solution to the first version of the problem.

The Problem

Assume that we are given a set of coins having the values {1, 3, 6}. To make a sum of 7 using these coins, all possible solutions are: {1,1,1,1,1,1,1}, {1,3,3}, and {1,6}. So the minimum number of coins required are 2, i.e. {1,6}. We reached our answer intuitively, but this wouldn’t work if there were too many denominations and a large sum was to be made.

Solution

One approach would be to generate all possible ways a sum can be made, and then choosing the one with the least number of coins. This, unlike Dynamic Programming, is computationally expensive.

Dividing into Subproblems

To implement Dynamic Programming, it is essential that you divide a problem into subproblems. We can view our problem as if we were to choose the better option from the following two options:

  1. Selecting the highest possible coin: The subproblem is about making the amount (Sum - the coin we added) with the same set of coins.
  2. Ignoring the highest possible coin: In this case, the subproblem is making the same sum with the original set of coins, minus the highest possible coin.

Choosing the better option in this problem equates to choosing the smaller of the two options. If the highest coin does not exceed the required sum, then we take the minimum of the two. Otherwise, we choose the second option and ignore the highest coin. Since that coin cannot be used in our solution, we act as if it doesn’t exist.

Recursive solution

The key part of a solution, when using DP, is to implement the array to keep track of the solutions to subproblems. This way, we won’t calculate what has already been done, again and again.

Each element of the 2-D array (arr) tells us the minimum number of coins required to make the sum j, considering the first i coins only.


Example

Supposing we have coins {1,5,6}. arr[2][15] = 3 means that we need at least 3 coins to make a sum of 15 if we only had the first 2 coins (i.e. {1,5}).

svg viewer

Following is the recursive solution to this problem:

if(coins[i] <= j){
    // Choosing the better of the two options:
    arr[i][j] = min(1 + arr[i][j - coins[i]], arr[i - 1][j]);
}
else{
    // Ignore the highest possible coin:
    arr[i][j] = arr[i - 1][j];
}
svg viewer
Explanation of the recursive solution

Implementation

  • In C++, the max value of an integer (INT_MAX) has been used to represent an undefined value.
  • In Java, double is used instead of int because we need to use the constant Double.POSITIVE_INFINITY when initialising the array.
#include <iostream>
#include <limits.h> 

using namespace std;

double findMin(double a, double b){
    if(a <= b)
        return a;
    else
        return b;
}

int findMinCoins(int coins[], int sum, int size){
    // Declaring 2-D array to store solutions to sub-problems:
    double** arr = new double*[size + 1];
    for(int i = 0; i < size + 1; i++)
        arr[i] = new double[sum + 1];
    
    // Initialising first column to zero
    // because a sum of zero is made with no coins:
    for(int i = 0; i < size + 1; i++)
        arr[i][0] = 0;
    
    // Initialising first row to INT_MAX (undefined)
    // because a sum cannot be made with zero coins:
    for(int j = 0; j < sum + 1; j++)
        arr[0][j] = INT_MAX;
    
    // Applying the recursive solution:
    for(int i = 1; i < size + 1; i++){
        for(int j = 1; j < sum + 1; j++){
            if(coins[i - 1] > j)  // cannot pick the highest coin:
                arr[i][j] = arr[i - 1][j];
            else  // choosing the best option:
                arr[i][j] = findMin(1 + arr[i][j - coins[i - 1]], arr[i - 1][j]);
        }
    }
    
    // Storing final answer:
    int answer = arr[size][sum];
    
    // Freeing up the memory from heap:
    for(int i = 0; i < size + 1; i++)
        delete[] arr[i];
    delete[] arr;
    
    return answer;
}

int main(){
    int coins[] = {5, 7, 8, 9};
    int sum = 49;
    
    // Finding total number of available coins:
    int size = sizeof(coins) / sizeof(coins[0]);
    
    cout << "At least " << findMinCoins(coins, sum, size) <<
    " coins are required to make a value of " << sum << endl;
    
    return 0;
}

RELATED TAGS

coin
change
problem
memoization
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring