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

1. 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`.
2. Initialize `ways = 0` since there are no ways to create a `\$0` target.
3. The significance of the `ways` array is simple, every index donates the target element for that particular value. For example, `ways` denotes what is the minimum number of ways to make `\$3` with whatever we have now. This will eventually build up to `ways` which is what we are looking for.
4. Iterate over the `coins` array to loop over current coin being traversed.
5. 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 = Math.min(ways, 1 + ways[3 - 1]`

This builds up to `ways` 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

## Practice all the solutions below

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