Making Change Algorithm
Published: 2021-03-25 17:04:07

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:

```jsx
// 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
```

```jsx
// 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

```jsx
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:

```javascript
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. 

```javascript
// ... 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. 

```javascript
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. 

```javascript
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`

```javascript
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!