Coin Change

Try to solve the Coin Change problem.

We'll cover the following

Statement#

You're given an integer total and a list of integers called coins. The variable coins hold a list of coin denominations, and total is the total amount of money.

You have to find the minimum number of coins that can make up the total amount by using any combination of the coins. If the amount can't be made up, return -1. If the total amount is 0, return 0.

Note: You may assume that we have an infinite number of each kind of coin.

Constraints:

  • 1≤1 \leq coins.length ≤12\leq 12

  • 1≤1 \leq coins[i] ≤104\leq 10^4

  • 0≤0 \leq total ≤900\leq 900

Examples#

Created with Fabric.js 3.6.6 total 7 2 coins 1 3 4 5 Inputs Output Sample example 1 Denominations = 4 + 3

1 of 4

Created with Fabric.js 3.6.6 2 Inputs Output total 4 coins 2 Sample example 2 Denominations = 2 + 2

2 of 4

Created with Fabric.js 3.6.6 Inputs Output coins 5 total 4 -1 Sample example 3 Denominations = None

3 of 4

Created with Fabric.js 3.6.6 Inputs Output coins 1 3 5 total 0 0 Sample example 4 Denominations = 0

4 of 4

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Coin Change

1

What is the minimum number of coins required to make up the following total with the set of coins available to us?

coins = [1, 2, 3, 4] total = 11

A)

-1

B)

3

C)

11

Question 1 of 20 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Initialize a counter array that contains elements equal to our total. Furthermore, initialize a variable to store the minimum number of coins needed. The minimum variable can be initialized to infinity at the start of each path.

Traverse the coins array, and for each element, check the base cases. If the remaining sum is equal to 0, return 0. If it is less than 0, return -1 and if it is greater than 0, return the target value stored at the - ithi^{th} index of the counter array. Store this value into a separate variable called result.

Increment the value in result variable by one and add it to the minimum variable. Repeat this process until the (rem-1)^{th} index of the counter is not infinity.

Try it yourself#

Implement your solution in main.py in the following coding playground.

Python
usercode > main.py
Input #1
Input #2
%0 node_01 1 node_11 2 node_21 5
Visualization for Input #1
Coin Change

Dynamic Programming: Introduction

Solution: Coin Change