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] = 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[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.
  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[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

Practice all the solutions below

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