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.

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,**. This will eventually build up to`ways[3]`

denotes what is the minimum number of ways to make`$3`

with whatever we have now`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.

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

.

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

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