DEV Community

Quinn Lashinsky
Quinn Lashinsky

Posted on

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!

Top comments (0)

Read next

jetthoughts-dev profile image

Stop Looking for Product Market Fit

JetThoughts Dev -

abhay_yt_52a8e72b213be229 profile image

Master Docker Attach: Real-Time Interaction with Running Containers

Abhay Singh Kathayat -

574n13y profile image

Introduction to GraphQL

Vivesh -

abhay_yt_52a8e72b213be229 profile image

Mastering Docker Exec: Interact with Running Containers Like a Pro

Abhay Singh Kathayat -