1.
Introduction
2.
Problem Statement
3.
Example
4.
Approach 1: Using Recursion
4.1.
Algorithm
4.2.
Dry Run
4.3.
Implementation
4.4.
C++
4.5.
C#
4.6.
Java
4.7.
Javascript
4.8.
Python
4.9.
PHP
4.10.
Complexity Analysis
5.
Approach 2: Using Dynamic Programming (Top Down/ Memoization)
5.1.
Implementation
5.2.
C++
5.3.
Java
5.4.
Python
5.5.
Javascript
5.6.
C#
5.7.
PHP
5.8.
Complexity Analysis
6.
Approach 3: Using Dynamic Programming (Bottom Up Approach/ Tabulation)
6.1.
Algorithm
6.2.
Implementation
6.3.
C++
6.4.
Java
6.5.
Python
6.6.
Javascript
6.7.
C#
6.8.
PHP
6.9.
Complexity Analysis
7.
Approach 4: Using Optimized DP
7.1.
Algorithm
7.2.
Implementation
7.3.
C++
7.4.
Java
7.5.
Python
7.6.
Javascript
7.7.
C#
7.8.
PHP
7.9.
Complexity Analysis
8.
8.1.
What is the minimum coin problem in Java?
8.2.
What is the coin changing problem?
8.3.
What is the time complexity of the minimum coin change problem?
8.4.
What are the applications of the coin change problem?
9.
Conclusion
Last Updated: Jun 23, 2024
Medium

# Coin Change: Minimum Number Of Coins

Rhythm Jain
0 upvote

## Introduction

The coin change problem has a variant known as the minimum number of coins problem. The aim is to determine the smallest number of coins required to equal a particular value. Only coins from a specific array should be used.

In this blog, we will discuss a problem Coin Change: Minimum number of coins. This is the most important question which is asked frequently in interviews.

Let’s understand the problem statement of coin change problem.

## Problem Statement

You are given an integer array of coins representing coins of different denominations and an integer amount representing a total amount of money. You have to return the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, you will return -1. You may assume that you have an infinite number of each kind of coin.

Let’s see an example to clearly understand this Coin Change Problem.

## Example

Suppose You are given an array of coins:

Now the amount you have to make is 11.

We can observe that there are multiple ways to make a total of 11 from given coin denominations.

So you can see that the minimum number of coins that will be used is 3 i.e. (5 + 5 + 1) or (5+3+3). Hence you have to return 3 as output.

Since you have understood the problem clearly. Now is the time to move towards the solution

## Approach 1: Using Recursion

On each element in the coins array, you have two choices whether it will be included to reach the amount or it will not be included. Remember whenever you have choices, that’s a clear indication that the problem can be solved using Recursion.

Let’s see the algorithm in steps for this coin change problem:

### Algorithm

1. We will decide on a base case first. The base case will be that suppose the size of the ‘coins’ array is zero and the amount you have to make is also zero, then you will return 0 because to make zero amount zero coins are sufficient else we will return -1.

2. Now on each coin in coins array we will decide:
• That this coin will be used in making the amount and will do amount - coins[i]
• That this coin will not be used in making the amount and will do start + 1.

3. Now add 1 in the first recursive call since you decided in that call that you are taking that coin and return the minimum of the answers received by recursive calls.

Now let’s see that how it looks in code

### Dry Run

Just shown the glimpse of the recursion tree, hope you guys have understood the idea/logic behind the recursive calls

• C++
• C#
• Java
• Javascript
• Python
• PHP

### C++

``#include <bits/stdc++.h>using namespace std;int coinChangeHelper(vector < int > & coins, int start,int amount) {   //  Base Case   if (start > coins.size()-1) {       if (amount == 0) {           return 0;       }       return -1;   }   // If amount is negative   if (amount < 0) {       return -1;   }   // Recursive calls   int ans1 = coinChangeHelper(coins, start, amount - coins[start]);   int ans2 = coinChangeHelper(coins, start + 1,  amount);   if (ans1 != -1 && ans2 != -1) {       return min(ans1 + 1, ans2);   }   // If we cannot achieve that amount through recursive call 1   if (ans1 == -1) {       return ans2;   }   // If we cannot achieve that amount through recursive call 2   if (ans2 == -1) {       return (ans1 + 1);   }   return -1;}int coinChange(vector < int > & coins, int amount) {   return coinChangeHelper(coins, 0, amount);}int main() {   vector < int > coins={1,3,5};   int amount=11;   // Calling the function   cout << coinChange(coins, amount);   return 0;}``

### C#

``using System;using System.Collections.Generic;class Program{    static int CoinChangeHelper(List<int> coins, int start, int amount)    {        // Base Case        if (start >= coins.Count)        {            return amount == 0 ? 0 : -1;        }        // If amount is negative        if (amount < 0)        {            return -1;        }        // Recursive calls        int ans1 = CoinChangeHelper(coins, start, amount - coins[start]);        int ans2 = CoinChangeHelper(coins, start + 1, amount);        if (ans1 != -1 && ans2 != -1)        {            return Math.Min(ans1 + 1, ans2);        }        // If we cannot achieve that amount through recursive call 1        if (ans1 == -1)        {            return ans2;        }        // If we cannot achieve that amount through recursive call 2        if (ans2 == -1)        {            return ans1 + 1;        }        return -1;    }    static int CoinChange(List<int> coins, int amount)    {        return CoinChangeHelper(coins, 0, amount);    }    static void Main(string[] args)    {        List<int> coins = new List<int> { 1, 3, 5 };        int amount = 11;        // Calling the function        Console.WriteLine(CoinChange(coins, amount));    }}``

### Java

``import java.util.*;public class Main {    public static int coinChangeHelper(List<Integer> coins, int start, int amount) {        // Base Case        if (start >= coins.size()) {            return amount == 0 ? 0 : -1;        }        // If amount is negative        if (amount < 0) {            return -1;        }        // Recursive calls        int ans1 = coinChangeHelper(coins, start, amount - coins.get(start));        int ans2 = coinChangeHelper(coins, start + 1, amount);        if (ans1 != -1 && ans2 != -1) {            return Math.min(ans1 + 1, ans2);        }        // If we cannot achieve that amount through recursive call 1        if (ans1 == -1) {            return ans2;        }        // If we cannot achieve that amount through recursive call 2        if (ans2 == -1) {            return ans1 + 1;        }        return -1;    }    public static int coinChange(List<Integer> coins, int amount) {        return coinChangeHelper(coins, 0, amount);    }    public static void main(String[] args) {        List<Integer> coins = Arrays.asList(1, 3, 5);        int amount = 11;        // Calling the function        System.out.println(coinChange(coins, amount));    }}``

### Javascript

``function coinChangeHelper(coins, start, amount) {    // Base Case    if (start >= coins.length) {        return amount === 0 ? 0 : -1;    }    // If amount is negative    if (amount < 0) {        return -1;    }    // Recursive calls    let ans1 = coinChangeHelper(coins, start, amount - coins[start]);    let ans2 = coinChangeHelper(coins, start + 1, amount);    if (ans1 !== -1 && ans2 !== -1) {        return Math.min(ans1 + 1, ans2);    }    // If we cannot achieve that amount through recursive call 1    if (ans1 === -1) {        return ans2;    }    // If we cannot achieve that amount through recursive call 2    if (ans2 === -1) {        return ans1 + 1;    }    return -1;}function coinChange(coins, amount) {    return coinChangeHelper(coins, 0, amount);}// Calling the functionlet coins = [1, 3, 5];let amount = 11;console.log(coinChange(coins, amount));``

### Python

``def coin_change_helper(coins, start, amount):    # Base Case    if start >= len(coins):        return 0 if amount == 0 else -1    # If amount is negative    if amount < 0:        return -1    # Recursive calls    ans1 = coin_change_helper(coins, start, amount - coins[start])    ans2 = coin_change_helper(coins, start + 1, amount)    if ans1 != -1 and ans2 != -1:        return min(ans1 + 1, ans2)    # If we cannot achieve that amount through recursive call 1    if ans1 == -1:        return ans2    # If we cannot achieve that amount through recursive call 2    if ans2 == -1:        return ans1 + 1    return -1def coin_change(coins, amount):    return coin_change_helper(coins, 0, amount)# Calling the functioncoins = [1, 3, 5]amount = 11print(coin_change(coins, amount))``

### PHP

``<?phpfunction coinChangeHelper(\$coins, \$start, \$amount) {    // Base Case    if (\$start >= count(\$coins)) {        return \$amount == 0 ? 0 : -1;    }    // If amount is negative    if (\$amount < 0) {        return -1;    }    // Recursive calls    \$ans1 = coinChangeHelper(\$coins, \$start, \$amount - \$coins[\$start]);    \$ans2 = coinChangeHelper(\$coins, \$start + 1, \$amount);    if (\$ans1 != -1 && \$ans2 != -1) {        return min(\$ans1 + 1, \$ans2);    }    // If we cannot achieve that amount through recursive call 1    if (\$ans1 == -1) {        return \$ans2;    }    // If we cannot achieve that amount through recursive call 2    if (\$ans2 == -1) {        return \$ans1 + 1;    }    return -1;}function coinChange(\$coins, \$amount) {    return coinChangeHelper(\$coins, 0, \$amount);}// Calling the function\$coins = [1, 3, 5];\$amount = 11;echo coinChange(\$coins, \$amount);?>``

Output

``3``

### Complexity Analysis

Time Complexity: O(2 ^ N) where ‘N’ refers to the size of coins array. On each element, we have two choices whether to take or not include it, which is giving us exponential time complexity.

Space Complexity: O(N) where ‘N’ refers to the size of coins array. Due to recursion, we are consuming this space in the recursion call stack.

Now you can see that in this approach of the coin change, we are making overlapping recursive calls that are costing us time Complexity. So to solve this problem, we will store the result of each recursive call in an array, and before making a new recursive call, we will check if the answer of that recursive call is present in that array already; then, we can escape from making the same call again. This technique is called memoisation.

## Approach 2: Using Dynamic Programming (Top Down/ Memoization)

All the steps will be the same as approach 1; the only difference is that here we will make a 2D array to store the results of previous calls. The row of this 2D array will signify the size of the coins array, and the column will represent amounts.

Please try to code this approach yourself; you will only gain confidence for your interviews.

Okay, I hope you have tried coding it on your own. Now let’s see the way I have code:

• C++
• Java
• Python
• Javascript
• C#
• PHP

### C++

``#include <bits/stdc++.h>using namespace std; int coinChangeHelper(vector < int > & coins, int start,int amount, int ** mem) {     // Base Case    if (start > coins.size()-1) {        if (amount == 0) {            return 0;        }        return -1;    }        // If amount is negative    if (amount < 0) {        return -1;    }        // If result of that recursive call already present    if (mem[start][amount] != -1) {        return mem[start][amount];    }     // Recursive calls    int ans1 = coinChangeHelper(coins, start, amount - coins[start], mem);    int ans2 = coinChangeHelper(coins, start + 1, amount, mem);     if (ans1 != -1 && ans2 != -1) {        mem[start][amount] = min(ans1 + 1, ans2);        return mem[start][amount];    }    if (ans1 == -1) {        mem[start][amount] = ans2;        return mem[start][amount];    }    if (ans2 == -1) {        mem[start][amount] = (ans1 + 1);        return mem[start][amount];    }     return -1;} int coinChange(vector < int > & coins, int amount) {     // Forming the array for storing the results of the recursive calls    int ** mem = new int * [coins.size()];    for (int i = 0; i < coins.size(); i++) {        mem[i] = new int[amount + 1];        for (int j = 0; j <= amount; j++) {            mem[i][j] = -1;        }    }    return coinChangeHelper(coins, 0, amount, mem);} int main() {    vector < int > coins={1,3,5};     int amount=11;     // Calling the function    cout << coinChange(coins, amount);    return 0;}``

### Java

``import java.util.Arrays;import java.util.List;public class CoinChange {    public static int coinChangeHelper(List<Integer> coins, int start, int amount, int[][] mem) {        if (start > coins.size() - 1) {            return amount == 0 ? 0 : -1;        }        if (amount < 0) {            return -1;        }        if (mem[start][amount] != -1) {            return mem[start][amount];        }        int ans1 = coinChangeHelper(coins, start, amount - coins.get(start), mem);        int ans2 = coinChangeHelper(coins, start + 1, amount, mem);        if (ans1 != -1 && ans2 != -1) {            mem[start][amount] = Math.min(ans1 + 1, ans2);            return mem[start][amount];        }        if (ans1 == -1) {            mem[start][amount] = ans2;            return mem[start][amount];        }        if (ans2 == -1) {            mem[start][amount] = ans1 + 1;            return mem[start][amount];        }        return -1;    }    public static int coinChange(List<Integer> coins, int amount) {        int[][] mem = new int[coins.size()][amount + 1];        for (int i = 0; i < coins.size(); i++) {            Arrays.fill(mem[i], -1);        }        return coinChangeHelper(coins, 0, amount, mem);    }    public static void main(String[] args) {        List<Integer> coins = Arrays.asList(1, 3, 5);        int amount = 11;        System.out.println(coinChange(coins, amount));    }}``

### Python

``def coin_change_helper(coins, start, amount, mem):    if start > len(coins) - 1:        return 0 if amount == 0 else -1    if amount < 0:        return -1    if mem[start][amount] != -1:        return mem[start][amount]    ans1 = coin_change_helper(coins, start, amount - coins[start], mem)    ans2 = coin_change_helper(coins, start + 1, amount, mem)    if ans1 != -1 and ans2 != -1:        mem[start][amount] = min(ans1 + 1, ans2)        return mem[start][amount]    if ans1 == -1:        mem[start][amount] = ans2        return mem[start][amount]    if ans2 == -1:        mem[start][amount] = ans1 + 1        return mem[start][amount]    return -1def coin_change(coins, amount):    mem = [[-1] * (amount + 1) for _ in range(len(coins))]    return coin_change_helper(coins, 0, amount, mem)if __name__ == "__main__":    coins = [1, 3, 5]    amount = 11    print(coin_change(coins, amount))``

### Javascript

``function coinChangeHelper(coins, start, amount, mem) {    if (start > coins.length - 1) {        return amount === 0 ? 0 : -1;    }    if (amount < 0) {        return -1;    }    if (mem[start][amount] !== -1) {        return mem[start][amount];    }    let ans1 = coinChangeHelper(coins, start, amount - coins[start], mem);    let ans2 = coinChangeHelper(coins, start + 1, amount, mem);    if (ans1 !== -1 && ans2 !== -1) {        mem[start][amount] = Math.min(ans1 + 1, ans2);        return mem[start][amount];    }    if (ans1 === -1) {        mem[start][amount] = ans2;        return mem[start][amount];    }    if (ans2 === -1) {        mem[start][amount] = ans1 + 1;        return mem[start][amount];    }    return -1;}function coinChange(coins, amount) {    let mem = Array.from({ length: coins.length }, () => Array(amount + 1).fill(-1));    return coinChangeHelper(coins, 0, amount, mem);}let coins = [1, 3, 5];let amount = 11;console.log(coinChange(coins, amount));``

### C#

``using System;using System.Collections.Generic;class CoinChange {    public static int CoinChangeHelper(List<int> coins, int start, int amount, int[,] mem) {        if (start > coins.Count - 1) {            return amount == 0 ? 0 : -1;        }        if (amount < 0) {            return -1;        }        if (mem[start, amount] != -1) {            return mem[start, amount];        }        int ans1 = CoinChangeHelper(coins, start, amount - coins[start], mem);        int ans2 = CoinChangeHelper(coins, start + 1, amount, mem);        if (ans1 != -1 && ans2 != -1) {            mem[start, amount] = Math.Min(ans1 + 1, ans2);            return mem[start, amount];        }        if (ans1 == -1) {            mem[start, amount] = ans2;            return mem[start, amount];        }        if (ans2 == -1) {            mem[start, amount] = ans1 + 1;            return mem[start, amount];        }        return -1;    }    public static int CoinChange(List<int> coins, int amount) {        int[,] mem = new int[coins.Count, amount + 1];        for (int i = 0; i < coins.Count; i++) {            for (int j = 0; j <= amount; j++) {                mem[i, j] = -1;            }        }        return CoinChangeHelper(coins, 0, amount, mem);    }    static void Main() {        List<int> coins = new List<int> { 1, 3, 5 };        int amount = 11;        Console.WriteLine(CoinChange(coins, amount));    }}``

### PHP

``<?phpfunction coinChangeHelper(\$coins, \$start, \$amount, &\$mem) {    if (\$start > count(\$coins) - 1) {        return \$amount == 0 ? 0 : -1;    }    if (\$amount < 0) {        return -1;    }    if (\$mem[\$start][\$amount] != -1) {        return \$mem[\$start][\$amount];    }    \$ans1 = coinChangeHelper(\$coins, \$start, \$amount - \$coins[\$start], \$mem);    \$ans2 = coinChangeHelper(\$coins, \$start + 1, \$amount, \$mem);    if (\$ans1 != -1 && \$ans2 != -1) {        \$mem[\$start][\$amount] = min(\$ans1 + 1, \$ans2);        return \$mem[\$start][\$amount];    }    if (\$ans1 == -1) {        \$mem[\$start][\$amount] = \$ans2;        return \$mem[\$start][\$amount];    }    if (\$ans2 == -1) {        \$mem[\$start][\$amount] = \$ans1 + 1;        return \$mem[\$start][\$amount];    }    return -1;}function coinChange(\$coins, \$amount) {    \$mem = array_fill(0, count(\$coins), array_fill(0, \$amount + 1, -1));    return coinChangeHelper(\$coins, 0, \$amount, \$mem);}\$coins = [1, 3, 5];\$amount = 11;echo coinChange(\$coins, \$amount);?>``

Output

``3``

### Complexity Analysis

Time Complexity: O(N * A) where ‘N’ refers to the size of the array and ‘A’ refers to the amount. Here we are visiting a 2-D array of size N * A just once that’s why we are arriving at this time complexity.

Space Complexity: O(N * A) where ‘N’ refers to the size of the array and ‘A’ refers to the amount. We are consuming this space as a 2-D array to store the results of recursive calls.

Now we have discussed the recursive and memoized code. So, this is the time to move towards a Dynamic Programming solution.

Check out this problem - Minimum Coin Change Problem

## Approach 3: Using Dynamic Programming (Bottom Up Approach/ Tabulation)

To solve this problem using Dynamic Programming, we have to take a 2-D array where:

• Rows will signify the size of the array

• Columns will signify the amounts.

Now let’s understand this approach better with the help of the steps:

### Algorithm

1. Make a 2D array with N + 1  rows and amount + 1 columns because the amount can also be zero. Here N is the size of coins array.

2. Now see the case when we have a zero-sized array and have to return a minimum number of coins for zero amount. Then the answer should be 0. Right? So dp[0][0] = 0.

3. Suppose we have a zero-sized array and have to make an amount greater than 0. Then, there is no way to return a minimum no of coins. So just put -1 in these cases.

4. One more case will be that suppose you have an array of size greater than zero, but the amount we have to make is 0; then obviously, the output will be 0.

5. For the rest of the cases, we have to put a minimum of the two cases:
• When we are taking the current coin in our amount
• When we are not taking the current coin in our amount.

After these five steps, you will have your answer placed at dp[N][amount]. Yes! That simple it is. Now try coding it out.

• C++
• Java
• Python
• Javascript
• C#
• PHP

### C++

``#include <bits/stdc++.h>using namespace std;int coinChange(vector < int > & coins, int amount) { int n = coins.size(); // 2-D array for storing the results int ** dp = new int * [n + 1]; for (int i = 0; i <= n; i++) {   dp[i] = new int[amount + 1]; } // Traversing the 2-D dp array for (int i = 0; i <= n; i++) {   for (int j = 0; j <= amount; j++) {     // If size of the array is zero and amount is also zero     if (i == 0 && j == 0) {       dp[i][j] = 0;     }     // If size of the array is zero     else if (i == 0) {       dp[i][j] = -1;     }     // If the amount is zero     else if (j == 0) {       dp[i][j] = 0;     }    else {       /*           If the value of current coin is less than the amount           Then we can include the current coin in our ans.       */       if (j - coins[i - 1] >= 0) {         if (dp[i][j - coins[i - 1]] != -1 && dp[i - 1][j] != -1)           dp[i][j] = min(dp[i][j - coins[i - 1]] + 1, dp[i - 1][j]);         // If we can't take the current coin for making our amount         else if (dp[i][j - coins[i - 1]] == -1) {           dp[i][j] = dp[i - 1][j];         }        else if (dp[i - 1][j] == -1) {           dp[i][j] = (dp[i][j - coins[i - 1]] + 1);         }       }      else {         dp[i][j] = dp[i - 1][j];       }     }   } } return dp[n][amount];}int main() {   vector < int > coins={1,3,5};   int amount=11;   // Calling the function   cout << coinChange(coins, amount);   return 0;}``

### Java

``import java.util.Arrays;import java.util.List;public class CoinChange {    public static int coinChange(List<Integer> coins, int amount) {        int n = coins.size();        int[][] dp = new int[n + 1][amount + 1];        for (int i = 0; i <= n; i++) {            Arrays.fill(dp[i], -1);        }        dp[0][0] = 0;        for (int i = 1; i <= n; i++) {            dp[i][0] = 0;        }        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= amount; j++) {                if (j - coins.get(i - 1) >= 0 && dp[i][j - coins.get(i - 1)] != -1) {                    if (dp[i - 1][j] != -1) {                        dp[i][j] = Math.min(dp[i][j - coins.get(i - 1)] + 1, dp[i - 1][j]);                    } else {                        dp[i][j] = dp[i][j - coins.get(i - 1)] + 1;                    }                } else {                    dp[i][j] = dp[i - 1][j];                }            }        }        return dp[n][amount];    }    public static void main(String[] args) {        List<Integer> coins = Arrays.asList(1, 3, 5);        int amount = 11;        System.out.println(coinChange(coins, amount));    }}``

### Python

``def coin_change(coins, amount):    n = len(coins)    dp = [[-1] * (amount + 1) for _ in range(n + 1)]    dp[0][0] = 0    for i in range(1, n + 1):        dp[i][0] = 0    for i in range(1, n + 1):        for j in range(1, amount + 1):            if j - coins[i - 1] >= 0 and dp[i][j - coins[i - 1]] != -1:                if dp[i - 1][j] != -1:                    dp[i][j] = min(dp[i][j - coins[i - 1]] + 1, dp[i - 1][j])                else:                    dp[i][j] = dp[i][j - coins[i - 1]] + 1            else:                dp[i][j] = dp[i - 1][j]    return dp[n][amount]if __name__ == "__main__":    coins = [1, 3, 5]    amount = 11    print(coin_change(coins, amount))``

### Javascript

``function coinChange(coins, amount) {    let n = coins.length;    let dp = Array.from({ length: n + 1 }, () => Array(amount + 1).fill(-1));    dp[0][0] = 0;    for (let i = 1; i <= n; i++) {        dp[i][0] = 0;    }    for (let i = 1; i <= n; i++) {        for (let j = 1; j <= amount; j++) {            if (j - coins[i - 1] >= 0 && dp[i][j - coins[i - 1]] != -1) {                if (dp[i - 1][j] != -1) {                    dp[i][j] = Math.min(dp[i][j - coins[i - 1]] + 1, dp[i - 1][j]);                } else {                    dp[i][j] = dp[i][j - coins[i - 1]] + 1;                }            } else {                dp[i][j] = dp[i - 1][j];            }        }    }    return dp[n][amount];}let coins = [1, 3, 5];let amount = 11;console.log(coinChange(coins, amount));``

### C#

``using System;using System.Collections.Generic;class CoinChange {    public static int CoinChangeFunc(List<int> coins, int amount) {        int n = coins.Count;        int[,] dp = new int[n + 1, amount + 1];        for (int i = 0; i <= n; i++) {            for (int j = 0; j <= amount; j++) {                dp[i, j] = -1;            }        }        dp[0, 0] = 0;        for (int i = 1; i <= n; i++) {            dp[i, 0] = 0;        }        for (int i = 1; i <= n; i++) {            for (int j = 1; j <= amount; j++) {                if (j - coins[i - 1] >= 0 && dp[i, j - coins[i - 1]] != -1) {                    if (dp[i - 1, j] != -1) {                        dp[i, j] = Math.Min(dp[i, j - coins[i - 1]] + 1, dp[i - 1, j]);                    } else {                        dp[i, j] = dp[i, j - coins[i - 1]] + 1;                    }                } else {                    dp[i, j] = dp[i - 1, j];                }            }        }        return dp[n, amount];    }    static void Main() {        List<int> coins = new List<int> { 1, 3, 5 };        int amount = 11;        Console.WriteLine(CoinChangeFunc(coins, amount));    }}``

### PHP

``<?phpfunction coinChange(\$coins, \$amount) {    \$n = count(\$coins);    \$dp = array_fill(0, \$n + 1, array_fill(0, \$amount + 1, -1));    \$dp[0][0] = 0;    for (\$i = 1; \$i <= \$n; \$i++) {        \$dp[\$i][0] = 0;    }    for (\$i = 1; \$i <= \$n; \$i++) {        for (\$j = 1; \$j <= \$amount; \$j++) {            if (\$j - \$coins[\$i - 1] >= 0 && \$dp[\$i][\$j - \$coins[\$i - 1]] != -1) {                if (\$dp[\$i - 1][\$j] != -1) {                    \$dp[\$i][\$j] = min(\$dp[\$i][\$j - \$coins[\$i - 1]] + 1, \$dp[\$i - 1][\$j]);                } else {                    \$dp[\$i][\$j] = \$dp[\$i][\$j - \$coins[\$i - 1]] + 1;                }            } else {                \$dp[\$i][\$j] = \$dp[\$i - 1][\$j];            }        }    }    return \$dp[\$n][\$amount];}\$coins = [1, 3, 5];\$amount = 11;echo coinChange(\$coins, \$amount);?>``

Output

``3``

### Complexity Analysis

Time Complexity: O(N * A) where ‘N’ refers to the size of the array and ‘A’ refers to the amount. Here we are visiting a 2-D array of size N * A just once that’s why we are arriving at this time complexity.

Space Complexity: O(N * A) where ‘N’ refers to the size of the array and ‘A’ refers to the amount. We are consuming this space as a 2-D array to store the results of previous inputs.

## Approach 4: Using Optimized DP

In the previous dp approach, we can observe that the answer is only dependent on the previous dp array (dp[i][j] is dependent on the value of dp[i-1][j]). Thus we can reduce our answer to a single dp and optimise the space complexity.

### Algorithm

1. Initialize a dp array of “Amount+1” size with values equal to the maximum number of coins possible to make the current amount (initialize it with “Amount”)

2. Dp[i] represents minimum number of ways to make the ‘i’ amount.

3. Initialize dp[0]=0.

4. For each coin in the array, check all possible amounts where the coin can occur.

5. This way, the level wise update the number of ways to reach the ith amount.

• C++
• Java
• Python
• Javascript
• C#
• PHP

### C++

``#include <bits/stdc++.h>using namespace std;int coinChange(vector < int > & coins, int amount) {    int n = coins.size();        //checking if amount is already 0. Then return 0.    if(amount==0)        return 0;    /*        1-D array for storing the results and initializing it         to maximum number of coins possible.    */        vector<int> dp(amount+1,amount+1);        // dp[i] stores the result of the number of coins needed to make "i" amount.    /*        initializing dp[0]=0 because if amount is zero         there is only 1 way to get 0 amount and that is by         taking none of the available coins.    */        dp[0]=0;    // Traversing the the array    for (int i = 0; i < n; i++) {            /*        for each coin in the array, checking all possible         amounts where the coin can occur.     */    for (int j = coins[i]; j <= amount; j++) {        if(j-coins[i]>=0)                    //taking minimum of all possible answers.            dp[j]=min(dp[j],1+dp[j-coins[i]]);    }  }  return dp[amount];}int main() {    vector < int > coins={1,3,5};    int amount=11;    // Calling the function    cout << coinChange(coins, amount);    return 0;}``

### Java

``import java.util.Arrays;import java.util.List;public class CoinChange {    public static int coinChange(List<Integer> coins, int amount) {        int n = coins.size();        if (amount == 0) return 0;        int[] dp = new int[amount + 1];        Arrays.fill(dp, amount + 1);        dp[0] = 0;        for (int i = 0; i < n; i++) {            for (int j = coins.get(i); j <= amount; j++) {                dp[j] = Math.min(dp[j], 1 + dp[j - coins.get(i)]);            }        }        return dp[amount] > amount ? -1 : dp[amount];    }    public static void main(String[] args) {        List<Integer> coins = Arrays.asList(1, 3, 5);        int amount = 11;        System.out.println(coinChange(coins, amount));    }}``

### Python

``def coin_change(coins, amount):    n = len(coins)    if amount == 0:        return 0    dp = [amount + 1] * (amount + 1)    dp[0] = 0    for i in range(n):        for j in range(coins[i], amount + 1):            dp[j] = min(dp[j], 1 + dp[j - coins[i]])    return dp[amount] if dp[amount] <= amount else -1if __name__ == "__main__":    coins = [1, 3, 5]    amount = 11    print(coin_change(coins, amount))``

### Javascript

``function coinChange(coins, amount) {    let n = coins.length;    if (amount === 0) return 0;    let dp = new Array(amount + 1).fill(amount + 1);    dp[0] = 0;    for (let i = 0; i < n; i++) {        for (let j = coins[i]; j <= amount; j++) {            dp[j] = Math.min(dp[j], 1 + dp[j - coins[i]]);        }    }    return dp[amount] > amount ? -1 : dp[amount];}let coins = [1, 3, 5];let amount = 11;console.log(coinChange(coins, amount));``

### C#

``using System;using System.Collections.Generic;class CoinChange {    public static int CoinChangeFunc(List<int> coins, int amount) {        int n = coins.Count;        if (amount == 0) return 0;        int[] dp = new int[amount + 1];        Array.Fill(dp, amount + 1);        dp[0] = 0;        for (int i = 0; i < n; i++) {            for (int j = coins[i]; j <= amount; j++) {                dp[j] = Math.min(dp[j], 1 + dp[j - coins[i]]);            }        }        return dp[amount] > amount ? -1 : dp[amount];    }    static void Main() {        List<int> coins = new List<int> { 1, 3, 5 };        int amount = 11;        Console.WriteLine(CoinChangeFunc(coins, amount));    }}``

### PHP

``<?phpfunction coinChange(\$coins, \$amount) {    \$n = count(\$coins);    if (\$amount == 0) return 0;    \$dp = array_fill(0, \$amount + 1, \$amount + 1);    \$dp[0] = 0;    for (\$i = 0; \$i < \$n; \$i++) {        for (\$j = \$coins[\$i]; \$j <= \$amount; \$j++) {            \$dp[\$j] = min(\$dp[\$j], 1 + \$dp[\$j - \$coins[\$i]]);        }    }    return \$dp[\$amount] > \$amount ? -1 : \$dp[\$amount];}\$coins = [1, 3, 5];\$amount = 11;echo coinChange(\$coins, \$amount);?>``

Output

``3``

### Complexity Analysis

Time Complexity: O(N * Amount) where ‘N’ refers to the size of the array.

Space Complexity: O(Amount). Here we are not using any additional data structure, we are using only an array of “Amount” size to store the results.

### What is the minimum coin problem in Java?

Finding the least number of coins required to make a certain amount of money with a given set of coin denominations is known as the minimum coin problem in Java. This problem is frequently handled using dynamic programming or greedy algorithms.

### What is the coin changing problem?

The coin changing problem involves finding the minimum number of coins needed to make a specific amount using a given set of coin denominations. It is a classic problem in computer science and combinatorial optimization.

### What is the time complexity of the minimum coin change problem?

The time complexity of the minimum coin change problem is O(N * A) where ‘N’ refers to the size of the array and ‘A’ refers to the amount. Here we are visiting a 2-D array of size N * A just once that’s why we are arriving at this time complexity.

### What are the applications of the coin change problem?

The coin change problem has numerous applications, including currency exchange, vending machines, and financial resource allocation optimization. It also forms the basis for the solution of scheduling and knapsack problems and is used in algorithm creation.

## Conclusion

In this blog, I have discussed all three approaches for the problem of Coin Change: Minimum Number Of Coins. You can see that I keep optimizing my code so that I can eliminate overlapping recursive calls. Remember, in interviews; you are also expected to solve questions in a manner that starts from brute force and then keep optimizing the code.

Recommended Problems:

Also check out the Interview guide for Product Based Companies as well as some of the Popular interview problems from top tech companies like Amazon, Adobe, Google, Uber, Microsoft, etc.

Refer to our guided pathways on Code studio to learn more about DSACompetitive ProgrammingJavaScriptSystem DesignDSA C++etc. Enroll in our courses, and use the accessible sample exams and questions as a guide. For placement preparations, look at the interview experiences and interview package.

Live masterclass