Skip to content

Instantly share code, notes, and snippets.

@szabi84
Last active June 18, 2019 10:44
Show Gist options
  • Save szabi84/abb57d6505b3d4b1af9ca37ac4649772 to your computer and use it in GitHub Desktop.
Save szabi84/abb57d6505b3d4b1af9ca37ac4649772 to your computer and use it in GitHub Desktop.
const atm = (value, banknotes, count = 0, bestCount = -1) => {
const filteredBankNotes = banknotes.filter(note => note <= value);
for (let i = 0; i < filteredBankNotes.length; i++) {
if (filteredBankNotes[i] <= value) {
count++;
value -= filteredBankNotes[i];
if (bestCount !== -1 && count > bestCount) {
break;
}
const res = atm(value, filteredBankNotes, count, bestCount);
value += filteredBankNotes[i];
bestCount = res.bestCount;
if (res.count === -1) {
count--;
} else {
value = res.value;
count = res.count;
if (bestCount === -1 || (bestCount !== -1 && count < bestCount)) {
bestCount = count;
}
count--;
value += filteredBankNotes[i]
}
}
}
if (value > 0) {
return {
count: -1,
bestCount
};
}
return {
count,
value,
bestCount
};
};
console.log(atm(130, [100, 50, 20, 10]).bestCount);
console.log(atm(134, [100, 50, 20, 10]).bestCount);
console.log(atm(21, [10, 3, 2]).bestCount);
console.log(atm(47, [10, 9]).bestCount);
console.log(atm(47, [10, 9, 1]).bestCount);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment