Amazon Coin Change Problem — 1st round
Recently I got a chance to interview with Amazon and this is the 1st question I was asked. I am going to elaborate the program logic using Recursion, Memoization and Dynamic Programming .
I will also try to cover the topic of how to approach a Dynamic Programming problem as well while explaining the logic behind the problem.
To be honest it’s difficult to write a program using Dynamic programming without actually writing it in recursion or iterative approach first. Yes, with practice one can write the programs directly on Dynamic Programming because most of the problems out there are related.
Steps to writing a dynamic program -
- Write the logic using recursion/iterative approach
- Use Memoization with Recursion
- Modify the program to use Dynamic Programming.
Coin Change Problem
You are given an integer array representing coins of different denominations and an integer amount which represents the amount of money.
We need to find the number of ways in which we can select those coins to make up the amount of money given to us.
This is the basic idea of the question. Now there are two variants of this question :
- Infinite supply of coins (We will discuss this approach in detail)
- Finite supply of coins (I’ve provided the code using Recursion at the end of this article.)
Infinite supply of coins :
Example 1 :
Input : coins = [1,2,5] , amount = 4
Output : 3
Explanation : 2+2, 1+1+1+1+1, 2+1+1
Example 2 :
Input : coins = [1,2,3] , amount = 4
Output : 4
Explanation : 1+1+1+1, 2+2, 2+1+1, 3+1
Similar problems :
This problem could be rephrased in a lot of ways. For e.g. if you have to cover 100 units and you are allowed to move only 1 unit, 2 units, and 5 units at a time then the problem asks, how many ways are possible to cover that 100 units.
Implementation Explanation:
Input : coins = [1,2,3] , amount = 4
Output : 4
We need to find the number of ways we can select the coins to make up a total of 4.
Steps to write the recursive program :
- Find out the method arguments which are needed
- Find out the output/return type
- Find the base conditions
- Write the core logic
Core logic to find the solution :
To make amount 4, we can either include the individual elements in an array or can exclude it. Say the last element from the array {1, 2, 3} which is 3 can be a part of the solution or cannot be a part of the solution.
So we have 2 ways — either include it, or do not include the element in the solution
coinchangesolution(array, N, W) =
coinchangesolution(array, N, W - array[N-1])
+
coinchangesolution(array, N — 1, W )array is the coin denominators provided
N is the array size
W is the amount
Explanation for above logic -
coinchangesolution(array, N, W-array[N-1])
When we include the element, we will have to decrease the amount, because the coin has been included. Hence the third argument has W-array[N-1]. N-1 because the index of an array starts from 0. We are passing N as 2nd argument because it can be included again in the solution(example — 1+1+1+1) . 1 is included 4 times to make the solution
coinchangesolution(array, N - 1, W )
When we do not include the element, we just decrease the value of N by 1 , and pass the same amount, as the element is not included as part of the solution.
Output type An integer which will be the number of ways we can select coins to make the amount.
Base conditions :
- When amount == 0 , return 1 (because the element can be included)
- When N==0; return 0; (because the above condition is not fulfilled, and we have traversed the entire array)
- When amount<0; return 0 (because we have solution for which W has become negative) Example- if we include 2+2+2 as solution then W = 4 -2 -2 -2 = -2 . So when W is -ve , the solution or coin denominators chosen cannot be the correct solution.
Program :
public class CoinChange {
public static void main(String args[]) {
int[] arr = {1, 2, 3,4};
int W = 4;
int number_of_ways = coinchangesolution(arr, arr.length, W);
System.out.println("Number of ways : " + number_of_ways);
}
static int coinchangesolution(int arr[], int n, int W) {
if (W == 0) {
return 1;
}
if (n == 0) {
return 0;
}
if (W < 0) {
return 0;
}
return coinchangesolution(arr, n - 1, W)
+
coinchangesolution(arr, n, W - arr[n - 1]);
}
}Memoization
Memoization is a method used to store the results of previous function calls to speed up future calculations. If repeated function calls are made with the same parameters, we can store the previous values instead of repeating unnecessary calculations. This approach helps in decreasing time complexity of the program.
In the problem we are solving using recursion, the worst case time complexity is more , and there are logics which are computed again and again.
Example :
input arr = [1,2,3]
amount = 4
1 + 1 + 1 + 1 = 4
{1 + 1 } + 2= 4
In this we are again computing 1 + 1 (in brackets), what if 1+1 was stored somewehere.
We will create a static array which will store the already computed values, so that it could be used again.
int store[][] = new int[N+1][W+1]Program :
import java.util.Arrays;
public class CoinChangeMemoisation {
static int store[][];
public static void main(String args[]) {
int[] arr = {1, 2, 3};
int W = 4;
store = new int[arr.length + 1][W + 1];
for (int i = 0, len = store.length; i < len; i++)
Arrays.fill(store[i],-1);
int number_of_ways = coinchangesolution(arr, arr.length, W);
System.out.println("Number of ways : " + number_of_ways);
}
static int coinchangesolution(int arr[], int n, int W) {
if (W == 0) {
return 1;
}
if (n == 0) {
return 0;
}
if (W < 0) {
return 0;
}
if(store[n][W] != -1) {
return store[n][W];
}
return store[n][W] =
coinchangesolution(arr, n - 1, W)
+
coinchangesolution(arr, n, W - arr[n - 1]);
}
}Dynamic Programming
We will create a static array which will store the already computed values, so that it could be used again.
int store[][] = new int[N+1][W+1]
We will use 2 for loops to iterate over N and W
index i will be N
index j will be W
Store[i][j] will store the number of ways we can select coins to make up the amount
When i == 0 which means when N == 0, store[i][j] = 0;
Means the array is empty , so the number of solutions would be 0 as no coins can be selected to make the amount
When j == 0 which means when W == 0, store[i][j] = 1;
Means when amount = 0, there will always be 1 solution as none of the elements could be selected to make the amount i.e. an empty array of values
Program :
package com.mycompany.app.CoinChangeProblem;
public class CoinChangeDP {
public static void main(String args[]) {
int[] arr = {1, 2, 3};
int W = 4;
int number_of_ways = coinchangesolution(arr, arr.length, W);
System.out.println("Number of ways : " + number_of_ways);
}
static int coinchangesolution(int arr[], int N, int W) {
int store[][] = new int[N + 1][W + 1];
//i means N which is size of array
//j means W which is limit given in input
for (int i = 0; i < N + 1; i++) {
for (int j = 0; j < W + 1; j++) {
if (i == 0) {
store[i][j] = 0;
continue;
}
if (j == 0) {
store[i][j] = 1;
continue;
}
if (arr[i - 1] <= j) {
store[i][j] = store[i][j - arr[i - 1]]
+
store[i-1][j];
} else {
store[i][j] = store[i - 1][j];
}
}
}
return store[N][W];
}
}Explanation for the above logic : It’s pretty simple.
We have a 2d array. The rows (i) denote N and the columns (j) denote W. And we will need 2 for loops to iterate over them. Base conditions are same as used in recursion. If you’re not clear till here, please read the above explanation again.
Now we will discuss this part :
if (arr[i - 1] <= j) {
store[i][j] = store[i][j - arr[i - 1]]
+
store[i-1][j];
} else {
store[i][j] = store[i - 1][j];
}i denotes N. j denotes W.
If the arr[i-1] < = j; means that if the coin denomination at i-1 is smaller than amount i.e W;
If yes this can be a part of the solution.
If not, then this cannot be a part of the solution.
store[i][j] = store[i][j - arr[i - 1]]
+
store[i-1][j];If it can be a part of solution, then either it can be included in the solution or it cannot be included. If it is included then we will deduct the denomination from amount(W) and we can again include it. So this -
store[i][j - arr[i - 1]]If it not included then; we will just decrease the index of array which is i, and amount(W) will be same i.e j will be same. So this -
store[i-1][j];Else block is executed when the denominator is greater than or equal to amount(W). In this case, no changes in amount i.e. j. The change will only be in index i because we are not including the value, so we will decrease the index by 1.
else {
store[i][j] = store[i - 1][j];
}Finite Supply of coins (Recursion):
In this case the major change will be in the core logic - instead of using the same coin again we will decrease the value of N by 1. We cannot choose the same coin as part of the solution because in this case we have finite supply of coins.
Example :
int[] arr= {1, 2, 3};
amount= 4;
With infinite supply {1+1+1+1 } was a solution, so we were passing the same coin to recursion method without decreasing the value of N.
coinchangesolution(arr, n, W - arr[n - 1])With finite supply, once we select {1 + ……}as solution, there’s no way we can select 1 again because of finite coins. Hence we will do a N -1 in the 2nd parameter of recursive call. (Marked in Bold and Italic in code)
coinchangesolution(arr, n-1, W - arr[n - 1])Program:
public class CoinChangeFC {
public static void main(String args[]) {
int[] arr = {1, 2, 3};
int W = 4;
int number_of_ways = coinchangesolution(arr, arr.length, W);
System.out.println("Number of ways : " + number_of_ways);
}
static int coinchangesolution(int arr[], int n, int W ) {
if(W == 0) {
return 1;
}
if(n == 0) {
return 0;
}
if(arr[n - 1] <= W) {
return coinchangesolution(arr, n-1, W - arr[n - 1])
+ coinchangesolution(arr, n - 1, W);
} else {
return coinchangesolution(arr, n-1, W);
}
}
}DP :
public class CoinChangeDP {
public static int coinChange(int[] coins, int amount) {
int length = coins.length;
int dp[][] = new int[length+1][amount+1];
for(int i=0;i<=length;i++) {
for(int j=0;j<=amount;j++) {
if(j==0){
dp[i][j] = 1;
}
else if(i==0) {
dp[i][j] = 0;
}
else if(coins[i-1]<=j) {
dp[i][j] = dp[i-1][j-coins[i-1]]+ dp[i-1][j];} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[length][amount];
}
public static void main(String args[]) {
System.out.println(coinChange(new int[]{1,2,3,4},6)); // 2
}
}
Conclusion :
The dynamic programming concept may seem a bit tricky at first. However once you are comfortable writing the recursion code , then writing the same logic using dynamic paradigm becomes a lot easier. Keep on learningn and practicing. With time, it becomes easier .
It gets easier - BoJack Horseman (Season 2 Finale)
Please leave a comment if you have any questions . All the claps are highly appreciated. Thanks !
