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:
- Convert the
price
to cents - Convert each value in the
payment
array to cents - If
paymentInCents
equalspriceInCents
, return[0,0,0,0]
- Determine how much change I owe (If I paid less than the
priceInCents
, or more than thepriceInCents
)- If
paymentInCents
is greater thanpriceInCents
, buyer is owedpaymentInCents
minuspriceInCents
- If
paymentInCents
is less thanpriceInCents
, buyer is owedpaymentInCents
- If
- Create a
changeArray
to keep track of the amount of each denomination I am returning as change. - 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 be0
- 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 rightreduceRight
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!
Top comments (0)