Data Structures and Algorithms - Problem - 3 Coin Change challenge 2

In the previous coin challenge, We solved the problem where have an integer array of coins of different denominations and an integer amount representing an amount of money.  and have an infinite number of each coin, and the order of coins doesn't matter, What we need to return is the fewest number of coins that we need to make up that amount.

In this blog, We are going to see another famous coin challenge problem, 

Problem Statement:- Where we are given an integer array of coins representing coins of different denominations and an integer amount representing a total amount of money. 

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return 0. 

 Example 1:  
 Input: coins = [5,10]  and  amount = 8
 Output: 0 

In the above example, the Output is 0 because there is no way we can create any combination from the given array to sum 8.

 Example 2:  
 Input: coins = [1,5,10] and  amount = 8
 Output: 2

In example 2, the output is 2 because we can sum 8 in 2 ways from the given array.

 Option 1 :- 1+1+1+1+1+1+1+1 = 8  
 Option 2 :- 5+1+1+1 = 8  

Let's try to solve this in code using a Dynamic Programming approach.

Happy Coding and Keep Sharing!! Code Repo

Data Structures and Algorithms - Problem - 2 Coin Change challenge 1

In this blog, We are going to solve another Dynamic Programming problem using Brute Force and Memoization.

Problem Statement:- You have an integer array of coins of different denominations and an integer amount representing an amount of money.  You have an infinite number of each coin, and the order of coins doesn't matter.

What we need to return is the fewest number of coins that we need to make up that amount.

 Example 1: coins [10,20,50] and the amount is 100  
 Option 1 :- 10 x 10 = 100  
 Option 2 :- 20 x 5 = 100  
 Option 3 :- 50 x 2 = 100  
 Option 4 :- 10 x 8 + 20 x 1 = 100  

As we can see we computed four options by which we can get to 100 using available coins but what we need is the fewest, and in that case, Option 3 is our best option. Now let's understand how we can solve this using Dynamic Programming.

Let's see another example 

 Example 2: coins [10,30,40,50] and the amount is 70  
 Option 1 :- 10 x 7 = 70   
 Option 2 :- 50 x 1 + 10 x 2 = 70  
 Option 3 :- 40 x 1 + 30 x 1 = 70  

In example 2 the fewest coins we would require is 2 as per option 3.

Can we solve this problem using a Greedy algorithm? Which always starts with the biggest number that's why "GREEDY". 

In Example 2,  Option 2 is the example of being Greedy, Where we started with the biggest number but that took us 3 coins value to get the final result, and option 3 took 2 coins value to get the result, Which means the GREEDY algorithm is not we want to use here.

What other approach, we can use here, Dynamic Programming and Brute Force? let's try that. In order to use Bruteforce, We need to implement DFS (Depth First Search). 

What we are doing here is we are subtracting the coins {10,30,40,50} from 70 which is our total amount, and we will continue subtracting coins till we reach 0 or stop doing it if the output is negative. 

Let's see the code, and understand how we can solve this problem. In the below code,  we followed example 2 and the output is as expected.

We should try one more example and this time the coins[] = {1,2,3} and amount = 7.  The fewest coins combination would be 3 x 2 + 1 x 1 = 7, which means a total of 3 coins.

In the next blog, we will see another famous coin chance challenge.

Happy Coding and Keep Sharing!! Code Repo