Minimum Number Of Coins To Make Change

Given an array of coins or denominations and a target sum, calculate the minimum number of coins required to match the total. Note that the coins array will have denominations that are Infinitely available, i.e. coins can be repeated and added to calculate the target.

Dynamic Programming

We are going to use dynamic programming to build our ways array as we traverse the coins / denominations array.

Create a ways array which will hold all the numbers climbing upto the target element. For example, if the target = 6, then the ways array length of the array will be = 7 and the indices will reach till 6. Initialize all the values inside of the array with Infinity.
Initialize ways[0] = 0 since there are no ways to create a $0 target.
The significance of the ways array is simple, every index donates the target element for that particular value. For example, ways[3] denotes what is the minimum number of ways to make $3 with whatever we have now. This will eventually build up to ways[6] which is what we are looking for.
Iterate over the coins array to loop over current coin being traversed.
Iterate over the ways array and check IF THE CURRENT COIN DENOMINATION IS LESS THAN OR EQUAL TO THE INDEX / AMOUNT VALUE. If that is true, We implement the following formula to calculate the minimum value:

ways[amount] = 
    Math.min(ways[amount], 1 + ways[amount - coins[i]])

For example, If current coin being traversed is 1 and we are at 3 index for ways - the formula becomes:

ways[3] = Math.min(ways[3], 1 + ways[3 - 1]

This builds up to ways[6] which is returned at the end.

Time Complexity:

O(nd) Time: n is the target and d is the length of denominations array.
O(n) Space: Because we create a ways array of length n.

Solve Minimum Number Of Coins To Make Change on Algochurn

#Dynamic programming #Arrays #Arrays #Dynamic Programming #Google #Amazon #JP Morgan #Morgan Stanley #Delhivery

Practice all the solutions below

JavaScript (Node.js 12.14.0)

Algochurn Theme

Practice the most popular front-end questions asked in coding interviews with Frontend Churn

00:00:00

Expand Solution

Minimum Number Of Coins To Make Change

Given an array of coins or denominations and a target sum, calculate the minimum number of coins required to match the target. Note that the coins array will have denominations that are Infinitely available, i.e. coins can be repeated and added to calculate the target.

Example

Input

coins = [1, 2, 4]
target = 6

Output

Explanation

There are many ways to make target equal to 6 using available coins of [1, 2 , 4].

Adding $1 coin 6 times.
Adding $1 coin 4 tumes and $2 coins 2 times.

and so on till you get the minimum.

Adding $4 coin 1 time and $2 coin 1 time

The MINIMUM number of coins that can add up to the target sum is 2. This is obtained when we add $4 coin 1 time and $2 coin 1 time

Therefore, the answer is = 2.

Example

Input

const coins = [2, 3, 7, 8]
const target = 27

Output

The minimum number of coins required to make a target of 27 is 4. Which is obtained by adding $8 coin 3 times and $3 coin 1 time.

Constraints

1 <= coins.length <= 10
1 <= coins[i] <= 100
1 <= target <= 1000

Stuck? Check out hints

Can you create an array of length = target +1 and somehow construct your solution from there on? Can you try iterating over the coins array and see if you could use some mathematical formula to compute your results?

Think Dynamic Programming, Think bottom-up solution. Solve for ways[0], build for ways[target]

Uploaded by: Manu Arora

Share this problem on

#Dynamic programming #Arrays #Arrays #Dynamic Programming #Google #Amazon #JP Morgan #Morgan Stanley #Delhivery

Minimum Number Of Coins To Make Change

Dynamic Programming

Time Complexity:

Practice all the solutions below

Minimum Number Of Coins To Make Change

Example

Input

Output

Explanation

Example

Input

Output

Constraints

Stuck? Check out hints

Pages

Algochurn

Frontend Churn

Friends

Links