What is the logic required to obtain the coins used in my algorithm?

Question

I’m analyzing an algorithm that returns the minimum number of coins to be used from a penny value.

def numero_moedas(centavos):
    if centavos < 1:
        return 0

    moedas = [50, 25, 10, 5, 1]
    n_moedas = 0

    for moeda in moedas:
        n_moedas += centavos // moeda
        centavos = centavos % moeda
        if centavos == 0:
            break

    return n_moedas

However, I need to display which coins were used among the minimum number of coins. For example:

In[1]: numero_moedas(31)
Out[1]: 3, [25, 5, 1]

What would be the logic needed to obtain this list of coins used?

Answer 1

It depends on the way you want the output. If you intend to use a dictionary to associate the coins with the required number, simply replace the n_moedas, the logic is basically the same:

def numero_moedas(centavos):
    n_moedas_total = 0
    n_cada_moeda = {50: 0, 25: 0, 10: 0, 5: 0, 1: 0}

    if centavos < 1:
        return n_moedas_total, n_cada_moeda

    for moeda in n_cada_moeda:
        n_moedas = centavos // moeda
        centavos = centavos % moeda
        n_moedas_total += n_moedas
        n_cada_moeda[moeda] = n_moedas
        if centavos == 0:
            break

    return n_moedas_total, n_cada_moeda

Or for a result more like the question, create a list and add the currencies accounted for in your loop:

def numero_moedas(centavos):
    n_moedas_total = 0
    moedas_utilizadas = []

    if centavos < 1:
        return n_moedas_total, moedas_utilizadas

    moedas = [50, 25, 10, 5, 1]

    for moeda in moedas:
        n_moedas = centavos // moeda
        centavos = centavos % moeda
        n_moedas_total += n_moedas
        moedas_utilizadas.extend([moeda] * n_moedas)
        if centavos == 0:
            break

    return n_moedas_total, moedas_utilizadas