Minimum Number of Coins

Problem Explanation: You are given an array of coin denominations and a target amount. Write a function to determine the minimum number of coins required to make up the target amount. You may use each coin denomination an unlimited number of times.

Example:

Input: coins = [1, 2, 5] 

target = 11

Output: 3

Explanation: The minimum number of coins required to make up the target amount of 11 is 3. We can use one 5 cent coin, and three 2 cent coins to make up the total amount.

Expected Time Complexity: O(nm), where n is the number of coin denominations and m is the target amount.

Expected Space Complexity: O(m), where m is the target amount.

Constraints:

• The input array coins will contain at least one coin denomination.
• All coin denominations will be positive integers.
• The target amount will be a positive integer.
• It is guaranteed that it is possible to make up the target amount using the given coin denominations.

Kotlin Solution :

fun minNumberOfCoins(coins: IntArray, target: Int): Int {
    val dp = IntArray(target + 1) { target + 1 }
    dp[0] = 0

    for (i in 1..target) {
        for (j in coins.indices) {
            if (coins[j] <= i) {
                dp[i] = minOf(dp[i], dp[i - coins[j]] + 1)
            }
        }
    }

    return if (dp[target] > target) -1 else dp[target]
}
fun main() {
    val coins = intArrayOf(1, 2, 5)
    val target = 11

    val minCoins = minNumberOfCoins(coins, target)

    if (minCoins == -1) {
        println("It is not possible to make up the target amount.")
    } else {
        println("The minimum number of coins required is $minCoins.")
    }
}