Банкомат — выдача купюр

Задача

Вернуть массив номиналов для запрошенной суммы. Купюры максимально крупные, общее количество минимально. Формат от большего к меньшему: ['5000x1', '1000x3', ...].

Пример

const nominals = [5000, 2000, 1000, 500, 100];
 
atm(6700); // ['5000x1', '1000x1', '500x1', '100x2']

Решение

Оптимальное решение

// Жадный алгоритм (Greedy) — работает, т.к. номиналы кратны друг другу
//
// Временная сложность: O(k) — где k количество номиналов
// Пространственная сложность: O(k) — результирующий массив
 
const nominals = [5000, 2000, 1000, 500, 100];
 
function atm(sum) {
    const result = [];
 
    for (const nominal of nominals) { // O(k) — идём от крупных к мелким
        const count = Math.floor(sum / nominal);
 
        if (count > 0) {
            result.push(`${nominal}x${count}`);
            sum -= nominal * count;
        }
    }
 
    return result;
}

См. также

• find-max-count