Tutorial Playlist

Data Structure Tutorial

Overview

Arrays in Data Structures: A Guide With Examples

Lesson - 1

All You Need to Know About Two-Dimensional Arrays

Lesson - 2

All You Need to Know About a Linked List in a Data Structure

Lesson - 3

The Complete Guide to Implement a Singly Linked List

Lesson - 4

The Ultimate Guide to Implement a Doubly Linked List

Lesson - 5

The Fundamentals for Understanding Circular Linked List

Lesson - 6

The Ultimate Guide To Understand The Differences Between Stack And Queue

Lesson - 7

Implementing Stacks in Data Structures

Lesson - 8

Your One-Stop Solution for Stack Implementation Using Array

Lesson - 9

Your One-Stop Solution for Queue Implementation Using Array

Lesson - 10

Your One-Stop Solution to Learn Depth-First Search(DFS) Algorithm From Scratch

Lesson - 11

Your One-Stop Solution for Stack Implementation Using Linked-List

Lesson - 12

The Definitive Guide to Understand Stack vs Heap Memory Allocation

Lesson - 13

All You Need to Know About Linear Search Algorithm

Lesson - 14

All You Need to Know About Breadth-First Search Algorithm

Lesson - 15

A One-Stop Solution for Using Binary Search Trees in Data Structure

Lesson - 16

The Best Tutorial to Understand Trees in Data Structure

Lesson - 17

A Complete Guide to Implement Binary Tree in Data Structure

Lesson - 18

A Holistic Look at Using AVL Trees in Data Structures

Lesson - 19

All You Need to Know About Tree Traversal in Data Structure

Lesson - 20

The Best Guide You’ll Ever Need to Understand B-Tree in Data Structure

Lesson - 21

The Best Guide You'll Ever Need to Understand Spanning Tree in Data Structure

Lesson - 22

The Best and Easiest Way to Understand an Algorithm

Lesson - 23

Your One-Stop Solution to Understand Shell Sort Algorithm

Lesson - 24

Your One-Stop Solution to Quick Sort Algorithm

Lesson - 25

The Most Useful Guide to Learn Selection Sort Algorithm

Lesson - 26

Everything You Need to Know About Radix Sort Algorithm

Lesson - 27

Everything You Need to Know About the Counting Sort Algorithm

Lesson - 28

Everything You Need to Know About the Merge Sort Algorithm

Lesson - 29

Insertion Sort Algorithm: One-Stop Solution That Will Help You Understand Insertion Sort

Lesson - 30

Everything You Need to Know About the Bubble Sort Algorithm

Lesson - 31

The Best Guide You’ll Ever Need to Understand Bucket Sort Algorithm

Lesson - 32

Your One-Stop Solution to Understand Recursive Algorithm in Programming

Lesson - 33

The Definitive Guide to Understanding Greedy Algorithm

Lesson - 34

Your One-Stop Solution to Understand Backtracking Algorithm

Lesson - 35

The Fundamentals of the Bellman-Ford Algorithm

Lesson - 36

Your One-Stop Solution for Graphs in Data Structures

Lesson - 37

The Best Guide to Understand and Implement Solutions for Tower of Hanoi Puzzle

Lesson - 38

A Simplified and Complete Guide to Learn Space and Time Complexity

Lesson - 39

All You Need to Know About the Knapsack Problem : Your Complete Guide

Lesson - 40

The Fibonacci Series: Mathematical and Programming Interpretation

Lesson - 41

The Holistic Look at Longest Common Subsequence Problem

Lesson - 42

The Best Article to Understand What Is Dynamic Programming

Lesson - 43

A Guide to Implement Longest Increasing Subsequence Using Dynamic Programming

Lesson - 44

A Holistic Guide to Learn Stop Solution Using Dynamic Programming

Lesson - 45

One Stop Solution to All the Dynamic Programming Problems

Lesson - 46

Understanding the Fundamentals of Binomial Distribution

Lesson - 47

Here’s All You Need to Know About Minimum Spanning Tree in Data Structures

Lesson - 48

Understanding the Difference Between Array and Linked List

Lesson - 49

The Best Article Out There to Understand the B+ Tree in Data Structure

Lesson - 50

A Comprehensive Look at Queue in Data Structure

Lesson - 51

Your One-Stop Solution to Understand Coin Change Problem

Lesson - 52

The Best Way to Understand the Matrix Chain Multiplication Problem

Lesson - 53

Your One-Stop Solution to Learn Floyd-Warshall Algorithm for Using Dynamic Programming

Lesson - 54

The Best Tutorial You'll Ever Need for Queue Implementation Using Linked List

Lesson - 55
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.

Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

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.