Greedy Algorithm to find the minimum number of Coins in Kotlin

by

The greedy algorithm to find the minimum number of coins required to make a given amount of change involves selecting the largest denomination coin that is less than or equal to the remaining amount of change and subtracting it from the remaining amount, until the remaining amount becomes zero.

Here is the step-by-step process for the greedy algorithm:

  1. Initialize a list of available coin denominations in descending order.
  2. Initialize a variable to keep track of the total number of coins used to make the change.
  3. Initialize a variable to keep track of the remaining amount of change to be made.
  4. For each coin denomination in the list of available coins: a. Check if the current coin denomination is less than or equal to the remaining amount of change. b. If it is, subtract the current coin denomination from the remaining amount of change. c. Add 1 to the total number of coins used. d. Repeat steps a-c until the remaining amount of change is less than the current coin denomination.
  5. Return the total number of coins used.

For example, let’s say we want to make a change of 67 cents using coins of denominations 25, 10, 5, and 1 cents. Here’s how the algorithm would work:

  1. Initialize the list of available coins as [25, 10, 5, 1].
  2. Initialize the total number of coins used to 0.
  3. Initialize the remaining amount of change to 67.
  4. For the first coin denomination, 25: a. 25 is less than or equal to 67, so subtract 25 from the remaining amount of change (now 42). b. Add 1 to the total number of coins used (now 1). c. Repeat steps a-b until the remaining amount of change is less than 25. we get total number of coins used (now 2) and the remaining amount of change (now 17)
  5. For the next coin denomination, 10: a. 10 is less than or equal to 17, so subtract 10 from the remaining amount of change (now 7). b. Add 1 to the total number of coins used (now 3). c. Repeat steps a-b until the remaining amount of change is less than 10.
  6. For the next coin denomination, 5: a. 5 is less than or equal to 7, so subtract 5 from the remaining amount of change (now 2). b. Add 1 to the total number of coins used (now 4). c. Repeat steps a-b until the remaining amount of change is less than 5.
  7. For the next coin denomination, 1: a. 1 is less than or equal to 2, so subtract 1 from the remaining amount of change (now 26). b. Add 1 to the total number of coins used (now 5). c. Repeat steps a-b until the remaining amount of change is less than 1. after repeating we get total number of coins used (now 6).
  8. Return the total number of coins used, which is 6.

In this example, the greedy algorithm used 6 coins to make the change of 67 cents: 25, 25, 10, and 5.

Kotlin
fun minCoins(coins: List<Int>, amount: Int): Int {
    // sort the coins in descending order
    val sortedCoins = coins.sortedDescending()
    // initialize variables for the total number of coins used and the remaining amount of change
    var numCoins = 0
    var remainingAmount = amount
    // iterate through the available coins
    for (coin in sortedCoins) {
        // while the current coin denomination is less than or equal to the remaining amount of change
        while (coin <= remainingAmount) {
            // subtract the current coin denomination from the remaining amount of change
            remainingAmount -= coin
            // increment the total number of coins used
            numCoins++
        }
        // if the remaining amount of change is zero, we're done
        if (remainingAmount == 0) break
    }
    return numCoins
}


fun main(){
    val coins = listOf(25, 10, 5, 1)
	val amount = 67
	val numCoins = minCoins(coins, amount)
	println("The minimum number of coins needed to make $amount cents is $numCoins.")
}

This function takes in a list of coin denominations in descending order and the amount of change needed, and returns the minimum number of coins required to make that amount of change using the given denominations.

This will output: The minimum number of coins needed to make 67 cents is 6.

Leave a Comment