Coin Change Algorithm Js

I have been trying to come up with a solution for this algorithm for 3-4 days but nothing seems to work and the available solutions are a bit more advanced for me. It has to be sol

Solution 1:

Simpler, reverse and map the denominations in cents and return a new array with the number of coins you need for each denomination.

const coinsCents = [1, 2, 5, 10, 20, 50, 100]
constgetChange = (amountInCents) => {
    return coinsCents.reverse().map(coin => {
        let amountCoin = Math.floor(amountInCents/coin)
        amountInCents -= amountCoin * coin
        return amountCoin
    }).reverse()
}

Solution 2:

With the denominations you have specified, the problem is simpler than the general change making problem. In this actual case we can be sure that using the largest denomination, that is not greater than the amount to pay, always leads to an optimal solution.

So then there is no need for recursion or dynamic programming. Just a simple loop will do.

I will here ignore the additional "layer" of getting the price of the bill and the amount that the customer pays. In the end the only thing that counts is the change amount to pay back to the customer. So this snippet asks for that change amount and returns the coins that need to be given as change.

functiongetChange(amount) {
    amount *= 100; // Convert to number of centsvar denominations = [1, 2, 5, 10, 20, 50, 100]; // centsvar result = [];
    while (amount > 0) {
        var coin = denominations.pop(); // Get next greatest coinvar count = Math.floor(amount/coin); // See how many times I need that coin
        amount -= count * coin; // Reduce the amount with that number of coinsif (count) result.push([coin/100, count]); // Store count & coin
    }
    return result;
}

// I/O management

change.oninput = function () {
    var coins = getChange(this.value);
    result.textContent = coins.map(([coin, count]) =>`${count} x $${coin}`).join(" + ");
};

To be paid to customer: <inputid="change"><div>Coins to pay: <spanid="result"></span></div>

Solution 3:

var coins;
var coinArray = {};
var output = {};


/* Method to get coin value without decimal point - it is required because 
* javascript will consider 5.6 as 6 if we do Math.round()
*/functiongetRoundFigureCoinValue(x) {
    return (x * 10 - ((x * 10) % 10)) / 10;
}

// Method to calculate possible combination of coinsfunctioncalculateCoins(input) {
    let largestPossibleCoin = 1;

    if (input) {
        coins.forEach((x) => {
            if (input >= x) {
                largestPossibleCoin = x;
            }
        });
        let remainingCents = input % largestPossibleCoin;
        output[largestPossibleCoin] = getRoundFigureCoinValue(
            (input / largestPossibleCoin).toFixed(1)
        );
        if (remainingCents && input > 1) {
            calculateCoins(remainingCents);
        }

        return largestPossibleCoin;
    }
}

// Method to be called to get output.functioncalculatePossibleCoinCombinations(value) {
    if (isNaN(value) || +value <= 0) {
        console.log('Invalid input');
        return;
    } else {
        console.log('Possible combinations are:')
        value = +value;
    }

    coins = [1, 5, 10, 25];
    while (coins.length) {
        let largestPossibleCoin = calculateCoins(value) || 0;
        let outputString = '';
        coins = coins.filter((x) => x < largestPossibleCoin);
        Object.keys(output).forEach((key) => {
            outputString += `${output[key]} - ${key} cents; `;
        })
        console.log(outputString);
        output = {};
    }
}


/*
Sample inputs:
 calculatePossibleCoinCombinations('89');
 calculatePossibleCoinCombinations(10);
 calculatePossibleCoinCombinations(0);
 calculatePossibleCoinCombinations('someString');
 calculatePossibleCoinCombinations(-10)
*/