Find the least number of coins required that can make any change from 1 to 99 cents

user_135318 0
Viewed 141964

Recently I challenged my co-worker to write an algorithm to solve this problem:

Find the least number of coins required that can make any change from 1 to 99 cents. The coins can only be pennies (1), nickels (5), dimes (10), and quarters (25), and you must be able to make every value from 1 to 99 (in 1-cent increments) using those coins.

However, I realized that I don't actually know how to do this myself without examining every possible combination of coins. There has to be a better way of solving this problem, but I don't know what the generic name for this type of algorithm would be called, and I can't figure out a way to simplify it beyond looking at every solution.

I was wondering if anybody could point me in the right direction, or offer up an algorithm that's more efficient.

algorithm performance
28 Answers

For this problem, Greedy approach gives a better solution than DP or others. Greedy approach: Find the largest denomination that is lesser than the required value and add it to the set of coins to be delivered. Lower the required cents by the denomination just added and repeat until the required cents becomes zero.

My solution (greedy approach) in java solution:

public class MinimumCoinDenomination {

    private static final int[] coinsDenominations = {1, 5, 10, 25, 50, 100};

    public static Map<Integer, Integer> giveCoins(int requiredCents) {
        if(requiredCents <= 0) {
            return null;
        }
        Map<Integer, Integer> denominations = new HashMap<Integer, Integer>();

        int dollar = requiredCents/100;
        if(dollar>0) {
            denominations.put(100, dollar);
        }
        requiredCents = requiredCents - (dollar * 100);

        //int sum = 0;
        while(requiredCents > 0) {
            for(int i = 1; i<coinsDenominations.length; i++) {
                if(requiredCents < coinsDenominations[i]) {
                    //sum = sum +coinsDenominations[i-1];
                    if(denominations.containsKey(coinsDenominations[i-1])) {
                        int c = denominations.get(coinsDenominations[i-1]);
                        denominations.put(coinsDenominations[i-1], c+1);
                    } else {
                        denominations.put(coinsDenominations[i-1], 1);
                    }
                    requiredCents = requiredCents - coinsDenominations[i-1];
                    break;
                }
            }
        }
        return denominations;
    }

    public static void main(String[] args) {
        System.out.println(giveCoins(199));
    }

}
user_29511510

In node.js

const calculateChange = (moneyIn, cost) => {
  const change = moneyIn - cost;
  const dollars = Math.floor(change);
  let remaining = change - dollars;
  const fifty_cents = remaining / 0.5;
  const fifty_cent_coins = Math.floor(fifty_cents);
  remaining = remaining - fifty_cent_coins * 0.5;
  const twenty_five_cents = remaining / 0.25;
  const twenty_five_cent_coins = Math.floor(twenty_five_cents);
  remaining = remaining - twenty_five_cent_coins * 0.25;
  const ten_cents = remaining / 0.1;
  const ten_cent_coins = Math.floor(ten_cents);
  remaining = remaining - ten_cent_coins * 0.1;
  const five_cents = remaining / 0.05;
  const five_cent_coins = Math.floor(five_cents);
  remaining = remaining - five_cent_coins * 0.05;
  const one_cents = remaining / 0.01;
  const one_cent_coins = Math.floor(one_cents);

  return [
    one_cent_coins,
    five_cent_coins,
    ten_cent_coins,
    twenty_five_cent_coins,
    fifty_cent_coins,
    dollars,
  ];
};
const change = calculateChange(3.14, 1.99);
console.log(change)
user_46191990
Related