course on Kotlin coding test, finding the minimum number of coins

Problem Description

When we have various coin values, we need to find the minimum number of coins required to make a specific amount. The goal is to minimize the number of coins needed to make the given amount.

Problem Input:

• Number of coin types N (1 ≤ N ≤ 100)
• Value of each coin Aᵢ (1 ≤ Aᵢ ≤ 10,000)
• Target amount M (1 ≤ M ≤ 1,000,000)

Problem Output:

Print the minimum number of coins required to make the target amount M. If it is not possible to make the amount, print -1.

Example

Input Example:

        3
        1
        3
        4
        6
        

Output Example:

        2
        

In the above example, there are 3 types of coins with values 1, 3, and 4. To make the target amount 6, we can use 2 coins by either (3 + 3) or (4 + 1 + 1).

Problem Solving Process

To solve this problem, we can use Dynamic Programming. Dynamic Programming is a technique to solve problems by reusing previous results, which can be very effectively applied in this problem.

1. Setting up the DP array

First, we declare a DP array to store the number of coins. DP[i] signifies the minimum number of coins needed to make amount i. During initialization, we set DP[0] to 0 and the rest to infinity (INF).

2. Defining the recurrence relation

We update the DP array by iterating over the values of each coin up to the amount M. Given a coin’s value, we start from that value and update the minimum number of coins for every possible amount.

The recurrence relation is as follows:

        DP[j] = min(DP[j], DP[j - coin] + 1)
        

Here, coin is the value of the currently considered coin.

3. Deriving the final result

After calculating the DP array for all coins and amounts, we check DP[M] to determine if that value is infinity (INF) or not. If it is infinity, we cannot make amount M, so we print -1; otherwise, we print the value of DP[M].

Code Implementation

fun minCoins(coins: IntArray, target: Int): Int {
    // Initialize the DP array to infinity
    val dp = IntArray(target + 1) { Int.MAX_VALUE }
    dp[0] = 0 // 0 coins are needed to make 0

    // Update the DP array for each coin value
    for (coin in coins) {
        for (j in coin..target) {
            if (dp[j - coin] != Int.MAX_VALUE) {
                dp[j] = Math.min(dp[j], dp[j - coin] + 1)
            }
        }
    }

    // Check the result
    return if (dp[target] == Int.MAX_VALUE) -1 else dp[target]
}

fun main() {
    // Input values
    val coins = intArrayOf(1, 3, 4)
    val target = 6
    val result = minCoins(coins, target)
    println(result) // Output: 2
}
        

Comparison and Optimization

The time complexity of this algorithm is O(N * M) and the space complexity is O(M). This algorithm is efficient in terms of time, especially when there are many coin types or the target amount is very large. However, there are ways to optimize the code further. For example, sorting the coin values in descending order and processing larger coins first can lead to faster results.

Various Cases

Here, we validate the performance of the algorithm through various input values. Testing different combinations of coin types and amounts to derive results is also an important step.

Case 1:

Input: 4, 2, 5, 7, target amount = 14

Output: 2 (using 2 coins of 7)

Case 2:

Input: 1, 3, 4, target amount = 11

Output: 3 (using 2 coins of 4 and 1 coin of 3)