Sha256: 7fbc46cdbd6a8bec4c5ddc6935b614cd5b9a6ed29818ec82fb44b18f6b8f0040
Contents?: true
Size: 1.2 KB
Versions: 163
Compression:
Stored size: 1.2 KB
Contents
class ChangeCalculator(coins: List<Int>) {
private val sortedCoins = coins.sorted()
fun computeMostEfficientChange(grandTotal: Int): List<Int> {
require(grandTotal >= 0) { "Negative totals are not allowed." }
val minimalCoinsMap = mutableMapOf<Int, List<Int>?>()
minimalCoinsMap.put(0, ArrayList())
for (total in 1..grandTotal) {
val minimalCoins = sortedCoins
.filter { it <= total }
.mapNotNull { coin ->
val minimalRemainderCoins = minimalCoinsMap[total - coin]
if (minimalRemainderCoins != null) prepend(coin, minimalRemainderCoins) else null
}
.sortedBy { it.size }
.firstOrNull()
minimalCoinsMap.put(total, minimalCoins)
}
return minimalCoinsMap[grandTotal] ?: throw IllegalArgumentException(
"The total $grandTotal cannot be represented in the given currency.")
}
private fun prepend(integer: Int, integers: List<Int>): List<Int> {
val result = mutableListOf<Int>()
result.add(integer)
result.addAll(integers)
return result
}
}
Version data entries
163 entries across 163 versions & 1 rubygems