JS Implementation of the Coin Change Algorithm

Question

JS Implementation of the Coin Change Algorithm

I've been grappling with this algorithm for the past few days, but unfortunately I haven't been able to come up with a successful solution yet. The available solutions seem to be too advanced for my current level of understanding. This problem must be solved using conditionals only; recursion and dynamic programming are not allowed.

The challenge is to determine the minimum number of coins needed to make change using the following denominations: 1, 0.5, 0.2, 0.1, 0.05, 0.02, and 0.01.

Here is the input required:

- Price of an item

- Total amount paid by the customer

My initial thoughts are as follows:

let price = +gets();
let paidSum = +gets();
// 'gets' is used to receive numerical input
let change = paidSum - price;

I was thinking that I could use Math.floor to extract the integer part and subtract it from the total change, but I'm unsure how to proceed with the remaining sum.

Would using modulo help me determine if the remaining sum includes any of the remaining change values, allowing me to subtract sequentially until reaching zero?

I understand that my question might not be perfectly articulated, but I really am stuck on this problem. I've managed to tackle every other task except this one. Thank you for your help.

javascript if-statement coin-change

Answer 1

Answer №1

Take a simpler approach by reversing and mapping the denominations in cents, resulting in a new array that indicates the number of coins needed for each denomination.

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

Answer 2

Take a simpler approach by reversing and mapping the denominations in cents, resulting in a new array that indicates the number of coins needed for each denomination.

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

Answer 3

Answer №2

When dealing with the specific denominations you have provided, solving this problem is not as complex as the general change making problem. In this scenario, it is guaranteed that utilizing the largest denomination equal to or less than the amount due will always result in an optimal solution.

Therefore, there is no necessity for recursion or dynamic programming. A straightforward loop suffices.

For the purpose of simplicity, I am overlooking the initial step of determining the bill's price and the customer's payment amount. Ultimately, what truly matters is the change that needs to be returned to the customer. This code snippet addresses that by calculating the required change amount and providing the corresponding coins for repayment.

function getChange(amount) {
    amount *= 100; // Convert to number of cents
    var denominations = [1, 2, 5, 10, 20, 50, 100]; // cents
    var result = [];
    while (amount > 0) {
        var coin = denominations.pop(); // Get next greatest coin
        var count = Math.floor(amount/coin); // See how many times I need that coin
        amount -= count * coin; // Reduce the amount with that number of coins
        if (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: <input id="change">
<div>Coins to pay: <span id="result"></span></div>

Answer 4

When dealing with the specific denominations you have provided, solving this problem is not as complex as the general change making problem. In this scenario, it is guaranteed that utilizing the largest denomination equal to or less than the amount due will always result in an optimal solution.

Therefore, there is no necessity for recursion or dynamic programming. A straightforward loop suffices.

For the purpose of simplicity, I am overlooking the initial step of determining the bill's price and the customer's payment amount. Ultimately, what truly matters is the change that needs to be returned to the customer. This code snippet addresses that by calculating the required change amount and providing the corresponding coins for repayment.

function getChange(amount) {
    amount *= 100; // Convert to number of cents
    var denominations = [1, 2, 5, 10, 20, 50, 100]; // cents
    var result = [];
    while (amount > 0) {
        var coin = denominations.pop(); // Get next greatest coin
        var count = Math.floor(amount/coin); // See how many times I need that coin
        amount -= count * coin; // Reduce the amount with that number of coins
        if (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: <input id="change">
<div>Coins to pay: <span id="result"></span></div>

Answer 5

Answer №3

let coinsList;
let coinMap = {};
let result = {};


/* Function to extract whole number value of a coin - necessary due to
* javascript rounding behavior where 5.6 is treated as 6 in Math.round()
*/
function getWholeNumberCoinValue(x) {
    return (x * 10 - ((x * 10) % 10)) / 10;
}

// Function to calculate possible combinations of coins
function calculateCoins(inputAmount) {
    let largestPossibleCoin = 1;

    if (inputAmount) {
        coinsList.forEach((coin) => {
            if (inputAmount >= coin) {
                largestPossibleCoin = coin;
            }
        });
        let remainingChange = inputAmount % largestPossibleCoin;
        result[largestPossibleCoin] = getWholeNumberCoinValue(
            (inputAmount / largestPossibleCoin).toFixed(1)
        );
        if (remainingChange && inputAmount > 1) {
            calculateCoins(remainingChange);
        }

        return largestPossibleCoin;
    }
}

// Main function call to generate output
function computePossibleCoinCombinations(value) {
    if (isNaN(value) || +value <= 0) {
        console.log('Invalid input');
        return;
    } else {
        console.log('Possible coin combinations are:');
        value = +value;
    }

    coinsList = [1, 5, 10, 25];
    while (coinsList.length) {
        let largestCoin = calculateCoins(value) || 0;
        let outputStr = '';
        coinsList = coinsList.filter((coin) => coin < largestCoin);
        Object.keys(result).forEach((key) => {
            outputStr += `${result[key]} - ${key} cents; `;
        });
        console.log(outputStr);
        result = {};
    }
}


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

Answer 6

let coinsList;
let coinMap = {};
let result = {};


/* Function to extract whole number value of a coin - necessary due to
* javascript rounding behavior where 5.6 is treated as 6 in Math.round()
*/
function getWholeNumberCoinValue(x) {
    return (x * 10 - ((x * 10) % 10)) / 10;
}

// Function to calculate possible combinations of coins
function calculateCoins(inputAmount) {
    let largestPossibleCoin = 1;

    if (inputAmount) {
        coinsList.forEach((coin) => {
            if (inputAmount >= coin) {
                largestPossibleCoin = coin;
            }
        });
        let remainingChange = inputAmount % largestPossibleCoin;
        result[largestPossibleCoin] = getWholeNumberCoinValue(
            (inputAmount / largestPossibleCoin).toFixed(1)
        );
        if (remainingChange && inputAmount > 1) {
            calculateCoins(remainingChange);
        }

        return largestPossibleCoin;
    }
}

// Main function call to generate output
function computePossibleCoinCombinations(value) {
    if (isNaN(value) || +value <= 0) {
        console.log('Invalid input');
        return;
    } else {
        console.log('Possible coin combinations are:');
        value = +value;
    }

    coinsList = [1, 5, 10, 25];
    while (coinsList.length) {
        let largestCoin = calculateCoins(value) || 0;
        let outputStr = '';
        coinsList = coinsList.filter((coin) => coin < largestCoin);
        Object.keys(result).forEach((key) => {
            outputStr += `${result[key]} - ${key} cents; `;
        });
        console.log(outputStr);
        result = {};
    }
}


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

JS Implementation of the Coin Change Algorithm

Answer №1

Answer №2

Answer №3

Similar questions

Changing the URL dynamically based on user interaction with jQueryLet's leverage the power of

What are the limitations when using React's forwardRef with Material UI's styled components?

Tips for sending a callback function in Angular following an HTTP request

Implementing dynamic title insertion into a popover element using jQuery

Utilizing Fullcalendar 5 in conjunction with Angular: Embedding Components within Events

Transferring information from Child to Parent using pure Javascript in VueJS

Receiving unexpected results when returning a function within a React hook

Leveraging NodeJS to handle server-side tasks and operations

Unable to interpret data from JSON file

When the form is submitted, I am unable to record the checkbox value

What are the key distinctions between an arrow function, a class, and a traditional function?

Guide on displaying a Custom 2D shape on both sides using three.js

Pair of dimensions painting with d3 version 4

The React component fails to inherit any props that are passed to it when it is rendered using a logical operator

When using React and React Router v6, make sure to implement a 404 status code response for unmatched routes

The information window is malfunctioning on Google Maps

What is the smallest server.js file needed to run a react/redux application?

Steps for triggering a click event on a div with a button role within a class containing multiple elements

What are some methods for creating a Venn Diagram that includes data within each section using SVG, CSS, or Canvas?

What is the reason for the request body being undefined?