The ATM Problem: Why the Greedy Algorithm Isn't an Optimal Solution

The ATM problem is a popular problem in FAANG interviews. It involves finding the minimum number of banknotes required to withdraw a certain sum of money from an ATM that contains banknotes of different denominations. In this article, we will explore the problem and its solution using the Greedy algorithm, as well as why the Greedy algorithm may not be suitable in all cases.

Problem Statement

Given an ATM containing N banknotes of different denominations, write a function that will withdraw the specified sum of money using the minimum possible number of banknotes. The function should return an array of numbers or null if the sum cannot be withdrawn.

Possible solutions

This problem can be solved in three different ways: using the Greedy algorithm, generating all possible combinations, or dynamic programming approach. In this article, we will focus on the Greedy algorithm, while the other solutions will be covered in separate articles.

Greedy Algorithm

The Greedy algorithm is an algorithm that takes locally optimal decisions at each step, assuming that the final overall solution will be optimal.

In this case, the Greedy algorithm can be expressed as follows:

1. Take the maximum banknote that is less than or equal to the required sum.
2. Record this banknote in the result and subtract it from the total sum.
3. Repeat step 1 until the entire sum has been withdrawn.

Example

Suppose the banknotes in the ATM are [5000, 1000, 500, 500, 100], and the sum to withdraw is 1600.

1. 5000 is not suitable as it is larger than the required sum.
2. 1000 is suitable (less than 1600), leaving a remainder of 600 (1600 - 1000).
3. 500 is suitable (less than 600), leaving a remainder of 100 (600 - 500).
4. 100 is suitable (equal to 100), leaving a remainder of 0 (100 - 100).
5. The remainder is 0, so the result is [1000, 500, 100].

Code

const withdraw = (total, _coins) => {
  // Sort the banknotes
  coins = _coins.slice().sort((a, b) => b - a);

  let res = [];
  let balance = total;

  // Iterate through all the banknotes
  for (let i = 0; i < coins.length; i++) {
    // If the banknote is larger than the required sum, skip it.
    if (coins[i] > balance) continue;

    res.push(coins[i]); // Record the banknote in the result.
    balance -= coins[i]; // Update the balance.

    // If the balance is zero, a solution has been found.
    if (balance === 0) {
      return res;
    };
  }

  return null;
};

The problem with the Greedy Algorithm

For the Greedy algorithm to give the optimal solution, it is necessary to be confident that the sequence of locally optimal choices will lead to a globally optimal solution. Unfortunately, the ATM problem does not always give an optimal solution when using the Greedy algorithm.

Example

Suppose the banknotes in the ATM are [1000, 800, 500, 100, 100, 100], and the sum to withdraw is 1300.

1. 1000 is suitable (less than 1300), leaving a remainder of 300 (1300 - 1000)

2. 800 is not suitable (larger than 300)

3. 500 is not suitable (larger than 300)

4. 100 is suitable (less than 300), leaving a remainder of 200 (300 - 100)

5. 100 is suitable (less than 200), leaving a remainder of 100 (200 - 100)

6. 100 is suitable (equals to 100), leaving a remainder of 0 (100 - 100)

7. The remainder is 0, so the result is [1000, 100, 100, 100]

The result [1000, 100, 100, 100] is not optimal because this amount can be issued with two banknotes [800, 500]. In the first step, we made a locally correct decision, but in the overall picture, this solution is suboptimal.

Summary

In conclusion, while the Greedy algorithm can provide an optimal solution for the ATM problem in most cases, there are situations where it fails to do so. Therefore, it cannot be used in a real ATM machine where accuracy and efficiency are critical. However, other approaches, such as dynamic programming, can help to solve this problem with a guaranteed optimal answer. In the next article, we will explore the dynamic programming approach and how it can be used to solve the ATM problem.

Lead image generated with stable diffusion.