# input:
# - one integer number K
#   (the total amount of change to give back)
# - an array V of values for the various kinds of
#   coints, SORTED FROM THE HIGHEST TO THE LOWEST VALUE
#
# output:
# - an array N of integers s.t. N[i] = j if
#   I am using j coins of type i
#
# constraint:
# - K = N[1]*V[1] + ... + N[n]*V[n]
#
# goal:
# - minimize  N[1] + ... + N[n]
#
# assumption:
# - the value of the coins is such that the greed algorithm
#   finds the optimal solution (e.g. multiples in base 10
#   of {1,2,5})
change_making(K,V) {
  N = [0,...,0]
  I := 1  // first element of the array
  while K > 0 {         // executed at most K times
    // we first look for the first coin whose value
    // is not above K, i.e. the largest coin we can use
    while V[I] > K
       I := I + 1
    N[I] := N[I] + (K / V[I])
    K := K % V[I]       // the reminder of the division
  }
  return N
}

# The inner loop is executed overall only at most |V|
# times. The outer loop as well because at every iteration
# of the outer loop the inner loop uses the next usable
# coin.
# Time complexity: O(|V|)