Untitled
unknown
java
3 years ago
1.3 kB
13
Indexable
package com.vortexalex.algos; /** * Calculate the minimum number of coins required to return an amount of change to the user. * For example, if a vending machine had available coins 1, 2, 5 and 10, the minimum number * of coins required to make up the change of 43 would be 6 (10, 10, 10, 10, 2, 1). * For simplicity, you have infinite number of available coins to give back. */ public class VendingMachine { public static int coins(int change, int[] availableCoins) { int minCoins = 0; int i = 0; while (change > 0) { int currentCoin; while ((currentCoin = availableCoins[i]) > change) { i++; } minCoins += change / currentCoin; change = change % currentCoin; } return minCoins; } public static int coinsRecursive(int change, int minCoins, int[] availableCoins) { if (change == 0) { return minCoins; } int[] newAvailableCoins = new int[availableCoins.length - 1]; System.arraycopy(availableCoins, 1, newAvailableCoins, 0, availableCoins.length - 1); return coinsRecursive(change % availableCoins[0], minCoins + (change / availableCoins[0]), newAvailableCoins); } }
Editor is loading...