How does an ATM withdrawal algorithm work?

The code to get money from the ATM should work like this:

// count of nominals in ATM
let limits = {
  1000: 5,
  500: 2,
  100: 5,
  50: 100,
  30: 6
}

let getMoney = (amount, limits) => {
  ...
};

console.log(getMoney(1000, limits)); // {1000: 1}
console.log(getMoney(230, limits)); // {} | i need {100: 2, 30: 1}
console.log(getMoney(200, limits)); // {100: 2}
console.log(getMoney(150, limits)); // {50: 3} | i need {100: 1, 50: 1}
console.log(getMoney(120, limits)); // {30: 4}

How does an ATM withdrawal algorithm work?

The code to get money from the ATM should work like this:

// count of nominals in ATM
let limits = {
  1000: 5,
  500: 2,
  100: 5,
  50: 100,
  30: 6
}

let getMoney = (amount, limits) => {
  ...
};

console.log(getMoney(1000, limits)); // {1000: 1}
console.log(getMoney(230, limits)); // {} | i need {100: 2, 30: 1}
console.log(getMoney(200, limits)); // {100: 2}
console.log(getMoney(150, limits)); // {50: 3} | i need {100: 1, 50: 1}
console.log(getMoney(120, limits)); // {30: 4}

I tried, and made this:

let getMoney = (am, lm) => {
  Object.keys(lm).map( k => {
    if(lm[k] && am / k >= 1 && am % k === 0)
      if(lm[k] > am / k)
        r[k] = am / k;
  });
};

...but the result is not correct:

console.log( getMoney(1000, limits) ); // {1000: 1}
console.log( getMoney(230, limits) ); // {} | i need {100: 2, 30: 1}
console.log( getMoney(200, limits) ); // {100: 2}
console.log( getMoney(150, limits) ); // {50: 3} | i need {100: 1, 50: 1}
console.log( getMoney(120, limits) ); // {30: 4}

How can I make it work?

• javascript
• algorithm
• limit

Share Improve this question Follow edited Mar 3, 2021 at 19:10 trincot 353k3737 gold badges273273 silver badges328328 bronze badges asked Mar 2, 2019 at 9:20 Alex MooreAlex Moore 4122 silver badges55 bronze badges 5

• 1 please add your try. what does not work? is it for school? – Nina Scholz Commented Mar 2, 2019 at 9:22
• 1 Also post what you have tried so far. – Anurag Srivastava Commented Mar 2, 2019 at 9:22
• I don't want to waste time to guess what mean of dict limits, plz add some ment to explain your algorithm – MoreFreeze Commented Mar 2, 2019 at 9:46
• @MoreFreeze i have added a ment – Alex Moore Commented Mar 2, 2019 at 10:02
• Thiat is a snapback problem, your algorithm doesn't work here. There are many probleams in your algorithm: 1. You don't do am -= am / k * k, if client need withdraw 230, and you find you can provide 2 pieces of 100, the rest you need calculate is 30 instead 230. 2. Greedy is not good here. It is easy to make some counterexample. Think about it. – MoreFreeze Commented Mar 2, 2019 at 10:09

Add a ment  | 

2 Answers 2

Sorted by: Reset to default 4

Your algorithm assumes that if there is a solution, then that solution will take the most of the highest available denomination that still fits the remaining amount. This would work for some sets of denominations, like the mon one (1000, 500, 200, 100, 50, 20, 10, 5, 2, 1), but not for the one in your example.

This is a variant of the change making problem and is a "hard" problem, in that you must potentially try a huge number of binations. One way is to at least give precedence to attempts that take a lot of the higher valued denominations, and only try alternatives when those do not lead to a solution.

You could code it like this:

let getMoney = (amount, limits) => {
    let recur = (amount, nominals) => {
        if (amount == 0) return {}; // success
        if (!nominals.length) return; // failure
        let nominal = nominals[0];
        let count = Math.min(limits[nominal], Math.floor(amount / nominal));
        for (let i = count; i >= 0; i--) {
            let result = recur(amount - i*nominal, nominals.slice(1));
            if (result) return i ? { [nominal]: i, ...result } : result;
        }
    }
    return recur(amount, Object.keys(limits).map(Number).sort((a,b) => b - a));
};

// count of nominals in ATM
let limits = { 1000: 5, 500: 2, 100: 5, 50: 100, 30: 6 }

console.log(getMoney(1000, limits)); // {1000: 1}
console.log(getMoney(230, limits)); // {30: 1, 100: 2}
console.log(getMoney(200, limits)); // {100: 2}
console.log(getMoney(150, limits)); // {50: 1, 100: 1}
console.log(getMoney(120, limits)); // {30: 4}

ATM denomination program in Javascript.

Here, It'll find the minimum number of notes of different denominations that sum the entered amount. Starting from the highest denomination note to the lowest notes.

Check this https://stackoverflow./a/66456375/9248245. This might helps others