Untitled

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);
    }
}