Making Change Algorithm

This past week I did a coding challenge that I actually enjoyed. The problem wasn't ridiculously abstract or one I would never solve if I were hired as a Junior Engineer. Below I'm gonna give the problem, show my pseudo-code, and then solve it. This may not be the best solution, but it works. I'd love to see other solutions. Write or link to your solution in the comments and feel free to add possible edge cases I may have missed.

The Problem

Given a payment array of US monetary denominations (i.e. 10.00 or .05), and the price of an item, calculate the least amount of coins a person should receive after paying for their item. If they do not input enough money, return their money in the least amount of coins possible. The coins given back should be formatted like this, [pennies, nickels, dimes, quarters].

For example:

// Can buy

// input
const price = 1.25
const payment = [.25, .50, .10, 1.00]

// output
makeChange(1.25, [.25, .50, .10, 1.00])
// [0, 1, 1, 0]

// 0 Pennies
// 1 Nickel
// 1 Dime
// 0 Quarters

// Cannot buy

// input 
const price = 1.50
const payment = [1.00, .10]

// output
makeChange(1.50, [1.00, .10])
// [0, 0, 1, 4]

// 0 Pennies
// 0 Nickels
// 1 Dime
// 4 Quarters

My Pseudo-Code

Here is the initial pseudo-code I came up with:

1. Convert the price to cents
2. Convert each value in the payment array to cents
3. If paymentInCents equals priceInCents, return [0,0,0,0]
4. Determine how much change I owe (If I paid less than the priceInCents, or more than the priceInCents)
   1. If paymentInCents is greater than priceInCents, buyer is owed paymentInCents minus priceInCents
   2. If paymentInCents is less than priceInCents , buyer is owed paymentInCents
5. Create a changeArray to keep track of the amount of each denomination I am returning as change.
6. Calculate change owed to our buyer for each denomination (quarters, dimes, nickels, pennies) in descending order. Put those values in their corresponding position ([pennies, nickels, dimes, quarters]). After we complete this process, the amount of change owed should be 0
7. Return changeArray, which is the amount of each denomination owed to the buyer.

My Solution

function makeChange(price, payment){

    const priceInCents = price * 100

    const paymentInCents = payment.reduce((acc, curr) => {
        return acc += curr * 100
    }, 0)

    if (priceInCents === paymentInCents){
        return [0, 0, 0, 0]
    }

    let changeOwed = priceInCents > paymentInCents 
        ? 
            paymentInCents 
        : 
            (paymentInCents - priceInCents)

    return calculateChangeOwed(changeOwed)
}

function calculateChangeOwed(changeOwed){
    let currentChangeOwed = changeOwed
    const changeArray = []

    const amountOfQuarters = Math.floor(currentChangeOwed / 25)
    currentChangeOwed -= (amountOfQuarters * 25)
    changeArray.unshift(amountOfQuarters)

    const amountOfDimes = Math.floor(currentChangeOwed / 10)
    currentChangeOwed -= (amountOfDimes * 10)
    changeArray.unshift(amountOfDimes)

    const amountOfNickels = Math.floor(currentChangeOwed / 5)
    currentChangeOwed -= (amountOfNickels * 5)
    changeArray.unshift(amountOfNickels)

    const amountOfPennies = Math.floor(currentChangeOwed / 1)
    currentChangeOwed -= (amountOfPennies * 1)
    changeArray.unshift(amountOfPennies)

    return changeArray
}

Some Explanations

Why Did I Convert All Monetary Values to Cents?

In Javascript mathematical operations with floating point numbers may lack numeric precision and may not give us the results we expect. For example:

console.log(40.90 * 3)
// 122.69999999999999

The output should be 122.7, right? Unfortunately, we can't expect Javascript to give us perfect representations of floats. Integers on the other hand can be represented perfectly, and converting all monetary values to cents will help us avoid floating point number issues.

Is This Code D.R.Y?

I repeat the same code 4 times while calculating how much of each currency is owed to the buyer.

// ... code ...

const amountOfQuarters = Math.floor(currentChangeOwed / 25)
    currentChangeOwed -= (amountOfQuarters * 25)
    changeArray.unshift(amountOfQuarters)

    const amountOfDimes = Math.floor(currentChangeOwed / 10)
    currentChangeOwed -= (amountOfDimes * 10)
    changeArray.unshift(amountOfDimes)

    const amountOfNickels = Math.floor(currentChangeOwed / 5)
    currentChangeOwed -= (amountOfNickels * 5)
    changeArray.unshift(amountOfNickels)

    const amountOfPennies = Math.floor(currentChangeOwed / 1)
    currentChangeOwed -= (amountOfPennies * 1)
    changeArray.unshift(amountOfPennies)

// ... more code ...

And I think it's entirely possible to clean this code up and make it better.

With reduce

If I create an array of each denomination I could possibly return in descending order I can use the reduce function to create an array of amount of each denomination owed to the buyer.

let currentChangeOwed = 155
let denominationArray = [25, 10, 5, 1]

denominationArray.reduce((acc, curr) => {
  const amountOfDenomination = Math.floor(currentChangeOwed / curr)
  currentChangeOwed -= (amountOfDenomination * curr)
  acc.unshift(amountOfDenomination)
  return acc
}, [])

With reduceRight

Not much different, but I think it's a bit more readable with all denominations in ascending order.

let currentChangeOwed = 155
let denominationArray = [1, 5, 10, 25]

denominationArray.reduceRight((acc, curr) => {
  const amountOfDenomination = Math.floor(currentChangeOwed / curr)
  currentChangeOwed -= (amountOfDenomination * curr)
  acc.unshift(amountOfDenomination)
  return acc
}, [])

What the Difference?

• reduce will traverse your array left to right

• reduceRight will traverse your array right to left

Full Code With reduceRight

function makeChange(price, payment){

    const priceInCents = price * 100

    const paymentInCents = payment.reduce((acc, curr) => {
        return acc += curr * 100
    }, 0)

    if (priceInCents === paymentInCents){
        return [0, 0, 0, 0]
    }

    const changeOwed = priceInCents > paymentInCents 
        ? 
            paymentInCents 
        : 
            (paymentInCents - priceInCents)

    return calculateChangeOwed(changeOwed)
}

function calculateChangeOwed(changeOwed){
    let currentChangeOwed = changeOwed
    const denominationArray = [1, 5, 10, 25]    


    const changeArray = denominationArray.reduceRight((acc, curr) => {
      const amountOfDenomination = Math.floor(currentChangeOwed / curr)
      currentChangeOwed -= (amountOfDenomination * curr)
      acc.unshift(amountOfDenomination)
      return acc
    }, [])

    return changeArray
}

Show your solutions in the comments!