Greedy Approach: Minimum Numbers of coins for a given amount

Find the minimum number of coins required to create a target sum. The given coins are real denominations.

To solve this problem we apply the greedy algorithm. We start from the highest value coin and take as much as possible and then move to less valued coins.

Algorithm:

1. Create an array named coin types to store all types of coins in Increasing order
2. Create a List<Integer> named coins to store the result, we are using a variable size array as we don’t know the size of the result
3. Iterate the coinTypes from end to start:
   1. While the target >= current coin type:
      1. Add the current coin type to the result
      2. Subtract the value of the current coin type from the target
4. return coins

Complexity:

Time Complexity: O(N) as we have to remove the coins one by one till the target is 0

Space Complexity: O(N)because of the List we are using to store the result

Java Code:

import java.util.ArrayList;
import java.util.List;


class Greedy {
   public static List<Integer> minPartition(int target) {
       // Create a array of all available coins
       int[] coinTypes = { 1, 2, 5, 10, 20, 50, 100, 200, 500, 2000 };

       // A list to store the coins required
       List<Integer> coins = new ArrayList<Integer>();

       // Iterate the array from the last element to the first element
       for (int i = coinTypes.length - 1; i >= 0; i--) {
           // Take the current coin till it is less than the target value
           while (target >= coinTypes[i]) {
               coins.add(coinTypes[i]);
               target -= coinTypes[i];
           }
       }

       // Return the final result
       return coins;
   }


   public static void main(String[] args) {
       int target = 175;
       List<Integer> result = minPartition(target);

       // Displaying the result
       System.out.println("Target: " + target);
       System.out.println("Min Coins: ");
       for (Integer i : result) {
           System.out.print(i + " ");
       }
   }
}

Output:

Target: 175

Min Coins: 

100 50 20 5