Coin Change: Minimum Number of Coins Problem

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

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

Implementation

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;
}

You can also try this code with Online C++ Compiler

Run Code

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));
    }
}

You can also try this code with Online Java Compiler

Run Code

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 function
let coins = [1, 3, 5];
let amount = 11;
console.log(coinChange(coins, amount));

You can also try this code with Online Javascript Compiler

Run Code

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 -1


def coin_change(coins, amount):
    return coin_change_helper(coins, 0, amount)


# Calling the function
coins = [1, 3, 5]
amount = 11
print(coin_change(coins, amount))

You can also try this code with Online Python Compiler

Run Code

PHP

<?php

function 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);

?>

You can also try this code with Online PHP Compiler

Run Code

Output

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:

Implementation

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;
}

You can also try this code with Online C++ Compiler

Run Code

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));
    }
}

You can also try this code with Online Java Compiler

Run Code

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 -1

def 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))

You can also try this code with Online Python Compiler

Run Code

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));

You can also try this code with Online Javascript Compiler

Run Code

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

<?php
function 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);
?>

You can also try this code with Online PHP Compiler

Run Code

Output

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

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

Implementation

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;
}

You can also try this code with Online C++ Compiler

Run Code

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));
    }
}

You can also try this code with Online Java Compiler

Run Code

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))

You can also try this code with Online Python Compiler

Run Code

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));

You can also try this code with Online Javascript Compiler

Run Code

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

<?php
function 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);
?>

You can also try this code with Online PHP Compiler

Run Code

Output

Complexity Analysis

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

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”)
Dp[i] represents minimum number of ways to make the ‘i’ amount.
Initialize dp[0]=0.
For each coin in the array, check all possible amounts where the coin can occur.
This way, the level wise update the number of ways to reach the ith amount.

Implementation

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;
}

You can also try this code with Online C++ Compiler

Run Code

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));
    }
}

You can also try this code with Online Java Compiler

Run Code

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 -1

if __name__ == "__main__":
    coins = [1, 3, 5]
    amount = 11
    print(coin_change(coins, amount))

You can also try this code with Online Python Compiler

Run Code

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));

You can also try this code with Online Javascript Compiler

Run Code

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

<?php
function 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);
?>

You can also try this code with Online PHP Compiler

Run Code

Output

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.

Frequently Asked Questions

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 DSA, Competitive Programming, JavaScript, System Design, DSA 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.