TheLazy.Dev
Portfolio GitHub

Blog

Making Change Algorithm

qmaximillian

Quinn Lashinsky

Posted on March 25, 2021

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
Enter fullscreen mode Exit fullscreen mode 
// 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
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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 ...
Enter fullscreen mode Exit fullscreen mode

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
}, [])
Enter fullscreen mode Exit fullscreen mode

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
}, [])
Enter fullscreen mode Exit fullscreen mode

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
}
Enter fullscreen mode Exit fullscreen mode

Show your solutions in the comments!

💖 💪 🙅 🚩
qmaximillian
Quinn Lashinsky

Posted on March 25, 2021

Join Our Newsletter. No Spam, Only the good stuff.

Sign up to receive the latest update from our blog.

Related

What was your win this week?
weeklyretro What was your win this week?

November 29, 2024

If you're a beginner, definitely check this open source guide. I've explained almost everything you need to know.
undefined If you're a beginner, definitely check this open source guide. I've explained almost everything you need to know.

November 28, 2024

Exploring Typesafe design tokens in Tailwind 4
tailwindcss Exploring Typesafe design tokens in Tailwind 4

November 29, 2024

The best way to get better at writing code is...
development The best way to get better at writing code is...

November 28, 2024

Where GitOps Meets ClickOps
devops Where GitOps Meets ClickOps

November 29, 2024