Your One-Stop Solution to Understand Coin Change Problem

Picture this, you are given an array of coins with varying denominations and an integer sum representing the total amount of money. You must return the fewest coins required to make up that sum; if that sum cannot be constructed, return -1. There are two solutions to the coin change problem: the first is a naive solution, a recursive solution of the coin change program, and the second is a dynamic solution, which is an efficient solution for the coin change problem. The time complexity of the coin change problem is (in any case) (n*c), and the space complexity is (n*c) (n).

Post Graduate Program: Full Stack Web Development

in Collaboration with Caltech CTMEEnroll Now
Post Graduate Program: Full Stack Web Development

What Is Dynamic Programming?

  • Dynamic Programming or DP is an algorithmic technique for solving optimization problems by breaking them down into simpler subproblems and exploiting the fact that the optimal solution to the overall situation is dependent on the optimal solution to its subproblems and taking advantage of the fact that the optimal solution to the overall situation is dependent on the optimal solution to its subproblems.
  • Dynamic Programming is a programming procedure that combines the precision of a complete search with the efficiency of greedy algorithms.
  • The main limitation of dynamic programming is that it can only be applied to problems divided into sub-problems. Furthermore, each of the sub-problems should be solvable on its own.
  • The concept of sub-problems is that these sub-problems can be used to solve a more significant problem. As a result, dynamic programming algorithms are highly optimized.
  • The goal of greedy algorithms is usually local optimization. The dynamic programming approach, on the other hand, attempts to optimize the problem as a whole.

Now that you have grasped the concept of dynamic programming, look at the coin change problem.

Introduction to Coin Change Problem

You are given an array of coins with varying denominations and an integer sum representing the total amount of money; you must return the fewest coins required to make up that sum; if that sum cannot be constructed, return -1.

coin-change-problem

Caltech Coding Bootcamp

Become a full stack developer in 6 monthsEnroll Now
Caltech Coding Bootcamp

Now, take a look at what the coin change problem is all about.

You are given a sequence of coins of various denominations as part of the coin change problem. For example, consider the following array a collection of coins, with each element representing a different denomination.

{ 2, 3, 5, 10, 20, 30, 50 };

Our goal is to use these coins to accumulate a certain amount of money while using the fewest (or optimal) coins. Furthermore, you can assume that a given denomination has an infinite number of coins. To put it another way, you can use a specific denomination as many times as you want.

For example, if you want to reach 78 using the above denominations, you will need the four coins listed below.

{ 3, 5, 20, 50 };

Consider the following another set of denominations:

{ 2, 3, 5, 6 };

If you want to make a total of 9, you only need two coins in these denominations, as shown below:

{ 3, 6 };

However, if you recall the greedy algorithm approach, you end up with three coins for the above denominations (5, 2, 2). This is due to the greedy algorithm's preference for local optimization.

After understanding a coin change problem, you will look at the pseudocode of the coin change problem in this tutorial.

New Course: Full Stack Development for Beginners

Learn Git Command, Angular, NodeJS, Maven & MoreEnroll Now
New Course: Full Stack Development for Beginners

Pseudocode of Coin Change Problem

The Coin Change Problem pseudocode is as follows:

  • Initialize a new array for dynamicprog of length n+1, where n is the number of different coin changes you want to find.
  • Because there is only one way to give change for 0 dollars, set dynamicprog[0] to 1.
  • Iterate through the array for each coin change available and add the value of dynamicprog[index-coins[i]] to dynamicprog[index] for indexes ranging from '1' to 'n'.
  • dynamicprog[n] return value

After understanding the pseudocode coin change problem, you will look at Recursive and Dynamic Programming Solutions for Coin Change Problems in this tutorial.

Solutions of Coin Change Problem

There are two solutions to the Coin Change Problem –

Recursion - Naive and slow approach.

Dynamic Programming – A timely and efficient approach

Now, look at the recursive method for solving the coin change problem and consider its drawbacks.

Coin Change Problem Solution Using Recursion

You have two options for each coin: include it or exclude it.

  • coins[] = {1, 2, 3}
  • sum = 4

When you include a coin, you add its value to the current sum solution(sol+coins[i], I, and if it is not equal, you move to the next coin, i.e., the next recursive call solution(sol, i++).

Total solutions are 4.

The diagram below depicts the recursive calls made during program execution.

recursive-solution-of-coin-change-problem

The recursive method causes the algorithm to calculate the same subproblems multiple times. Therefore, to solve the coin change problem efficiently, you can employ Dynamic Programming.

Full Stack Web Developer Course

To become an expert in MEAN StackView Course
Full Stack Web Developer Course

Coin Change Problem Solution Using Dynamic Programming

The dynamic approach to solving the coin change problem is similar to the dynamic method used to solve the 01 Knapsack problem.

To store the solution to the subproblem, you must use a 2D array (i.e. table). Then, take a look at the image below.

dynamic-programming-solution-using-coin-change-problem.

  • The size of the dynamicprogTable is equal to (number of coins +1)*(Sum +1).
  • The first column value is one because there is only one way to change if the total amount is 0. (we do not include any coin).
  • Row: The total number of coins. The fact that the first-row index is 0 indicates that no coin is available. If the value index in the second row is 1, only the first coin is available. Similarly, if the value index in the third row is 2, it means that the first two coins are available to add to the total amount, and so on. The row index represents the index of the coin in the coins array, not the coin value.
  • Column: Total amount (sum). Because the first-column index is 0, the sum value is 0. The second column index is 1, so the sum of the coins should be 1. Similarly, the third column value is 2, so a change of 2 is required, and so on.

As a result, each table field stores the solution to a subproblem. For example, dynamicprogTable[2][3]=2 indicates two ways to compute the sum of three using the first two coins 1,2.

The final outcome will be calculated by the values in the last column and row.

In this case, you must loop through all of the indexes in the memo table (except the first row and column) and use previously-stored solutions to the subproblems.

  • If the coin value is greater than the dynamicprogSum, the coin is ignored, i.e. dynamicprogTable[i][j]=dynamicprogTable[i-1][j].
  • If the coin value is less than the dynamicprogSum, you can consider it, i.e. dynamicprogTable[i][j]=dynamicprogTable[i-1].[dynamicprogSum]+dynamicprogTable[i][j-coins[i-1]].

You will look at the complexity of the coin change problem after figuring out how to solve it.

The Complexity of Coin Change Problem

  • The complexity of solving the coin change problem using recursive time and space will be:

Problems: Overlapping subproblems + Time complexity

O(2n) is the time complexity, where n is the number of coins

  • Time and space complexity will be reduced by using dynamic programming to solve the coin change problem:

O(numberOfCoins*TotalAmount) time complexity

O(numberOfCoins*TotalAmount) is the space complexity.

You will now see a practical demonstration of the coin change problem in the C programming language.

Code Implementation of Coin Change Problem

1. Recursive solution code for the coin change problem

#include <stdio.h>

int coins[] = {1,2,3};

int numberofCoins = 3, sum = 4;

 int solution(int sol, int i){

    if(numberofCoins == 0 || sol > sum || i>=numberofCoins)

        return 0;

    else if(sol == sum)

        return 1;

      return solution(sol+coins[i],i) + solution(sol,i+1) ;

}

int main()

{

    printf("Total solutions: %d",solution(0,0));

    return 0;

}

Output: 

code1-of-coin-change-problem

2. Dynamic Programming solution code for the coin change problem

#include <stdio.h>

int coins[] = {1,2,3}, sum=4;

int numberofCoins = 3;

//Function to initialize 1st column of dynamicprogTable with 1

void initdynamicprogTable(int dynamicprogTable[][5])

{

    int i;

    //First row to 0

    for(i=1; i<=sum+1; i++){

      dynamicprogTable[0][i] = 0;

    }

    //First column to 1

    for(i=1; i<=numberofCoins; i++){

      dynamicprogTable[i][0] = 1;

    }

}

int solution(int dynamicprogTable[][5]){

  int coinindex, dynamicprogSum;

  for(coinindex=1; coinindex<numberofCoins+1; coinindex++){

      for(dynamicprogSum=1; dynamicprogSum< 5; dynamicprogSum++){

        //value of coin should be less than or equal to sum value to consider it

        if(coins[coinindex-1] > dynamicprogSum)

            dynamicprogTable[coinindex][dynamicprogSum] = dynamicprogTable[coinindex-1][dynamicprogSum];

        else

            dynamicprogTable[coinindex][dynamicprogSum] = dynamicprogTable[coinindex-1][dynamicprogSum]+dynamicprogTable[coinindex][dynamicprogSum-coins[coinindex-1]];       

      }

  }

  //return final row and column value

  return dynamicprogTable[numberofCoins][sum];

}

int main()

{

    int dynamicprogTable[numberofCoins+1][5];

    initdynamicprogTable(dynamicprogTable);

    printf("Total Solutions: %d",solution(dynamicprogTable));

    return 0;

}

Output: 

/code2-dynamic-programming-solution.

Following the implementation of the coin change problem code, you will now look at some coin change problem applications.

Free Course: Programming Fundamentals

Learn the Basics of ProgrammingEnroll Now
Free Course: Programming Fundamentals

Applications of Coin Change Problem

This algorithm can be used to distribute change, for example, in a soda vending machine that accepts bills and coins and dispenses coins.

Buying a 60-cent soda pop with a dollar is one example. This leaves 40 cents to change, or in the United States, one quarter, one dime, and one nickel for the smallest coin pay. However, if the nickel tube were empty, the machine would dispense four dimes.

Last but not least, in this coin change problem article, you will summarise all of the topics that you have explored thus far.

Next Steps 

In the coin change problem, you first learned what dynamic programming is, then you knew what the coin change problem is, after that, you learned the coin change problem's pseudocode, and finally, you explored coin change problem solutions. After that, you learned about the complexity of the coin change problem and some applications of the coin change problem. Finally, you saw how to implement the coin change problem in both recursive and dynamic programming.

Suppose you want more that goes beyond Mobile and Software Development and covers the most in-demand programming languages and skills today. In that case, Simplilearn's Full Stack Development course is a good fit. 

Do you have any questions about this Coin Change Problem tutorial? If you do, please leave them in the comments section at the bottom of this page. Our experts will be happy to respond to your questions as earliest as possible!

About the Author

Kartik MenonKartik Menon

Kartik is an experienced content strategist and an accomplished technology marketing specialist passionate about designing engaging user experiences with integrated marketing and communication solutions.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.
  • *According to Simplilearn survey conducted and subject to terms & conditions with Ernst & Young LLP (EY) as Process Advisors