Простежимо, як змінюється запас п'ятиужикових монет в автоматі після кожної покупки. Склянка коштує ужиків, решту автомат видає лише п'ятірками, а отримані п'ятірки залишає собі.
Заплатили монетою : решти немає, монета залишається в автоматі — запас зростає на .
Заплатили : решта , тобто одна монета — запас зменшується на .
Заплатили : решта , тобто дев'ять монет — запас зменшується на .
Заплатили : решта , тобто дев'ятнадцять монет — запас зменшується на .
Купюри самі по собі для решти не годяться, тому вони запас не поповнюють.
Отже, якщо початково завантажити монет, то після -ї покупки запас дорівнює x + P_i, де P_i — префіксна сума описаних змін. Автомат працює коректно, якщо запас ніколи не стає від'ємним, тобто
Звідси мінімальна кількість монет для завантаження:
Реалізація — один прохід: ведемо поточну префіксну суму й запам'ятовуємо її мінімум. Складність — .
Зверніть увагу, що дивитися треба саме на мінімум по всіх префіксах, а не лише на кінцевий баланс: автомат може «просісти» посередині, навіть якщо в кінці монет вистачає.