Different implementations of `makeChange` problem.

make_change.js

// Write a function, makeChange, that returns an integer
// that represents the least number of coins that add up
// to an amount where the amount is always divisible by 5

const availableCoins = {
	5: 0,
	10: 0,
	25: 0
}

function makeChangeOne (inputAmount) {
	let count = 0
	while (inputAmount != 0) {
		if (inputAmount >= 25) {
			inputAmount -= 25
			count++
			availableCoins[25]++
			continue;
		}

		if (inputAmount >= 10) {
			inputAmount -= 10
			count++
			availableCoins[10]++
			continue;
		}

		if (inputAmount >= 5) {
			inputAmount -= 5
			count++
			availableCoins[5]++
			continue;
		}

	}
	return count
}


function makeChangeTwo(coins, amount) {
	coins.sort((x, y) => y - x);
	let total = 0;
	let i = 0;

	while (amount > 0) {
		if (coins[i] <= amount) {
			amount -= coins[i];
			total++;
		} else {
			i++
		}
	}
	return total;
}

function makeChange (value) {
	if (value === 0) return 0;
	let minCoins;
	coins.forEach(coin => {
		if (value-coin >= 0) {
			let currMinCoins = makeChange(value - coin);
			if (minCoins === undefined || currMinCoins < minCoins) {
				minCoins = currMinCoins
			}
		}
	});
	return minCoins + 1
}

function memoizeMakeChangeWithCache (coins) {
	const cache = {}

	return val => {
		if (cache[val]) return cache[val];

		let minCoins = -1;
		coins.forEach(coin => {
			if (val-coin >= 0) {
				let currMinCoins = makeChange(val - coin);
				if (minCoins === -1 || currMinCoins < minCoins) {
					minCoins = currMinCoins
				}
			}
		})

		// save the value inside the cache
		cache[val] = minCoins + 1

		return cache[val]
	}
}

console.log(makeChangeOne(35))
const coins = [1, 6, 10]
inputAmount = 12
console.log(makeChange(19))