Swift Coding Test Course, Greedy Algorithm

Problem: Coin Change

This problem involves finding the minimum number of coins needed to give change for a given amount, given the types of coins available in the store.

Problem Description:

• Input: Types of coins and the amount to be given as change.
• Output: Minimum number of coins

Example Input:

Types of coins: 1, 3, 4
Amount: 6

Example Output:

2 (3 + 3)

Problem Solving Process

1. Problem Analysis

The key to this problem is expressing the amount to be given as change using the minimum number of coins based on the types of coins available. The approach of selecting the largest coin first is efficient.

2. Approach

The basic approach to solving this is as follows:

1. Sort the given types of coins in ascending order.
2. Use as many of the largest coin as possible.
3. Repeat the above process for the remaining amount.
4. Continue this process until the amount to be given as change is 0.

3. Algorithm Implementation (Swift)

func minCoins(coins: [Int], amount: Int) -> Int {
    var remainingAmount = amount
    var coinCount = 0
    var sortedCoins = coins.sorted(by: { $0 > $1 }) // Sort in descending order
    
    for coin in sortedCoins {
        while remainingAmount >= coin {
            remainingAmount -= coin
            coinCount += 1
        }
    }
    return remainingAmount == 0 ? coinCount : -1 // Return -1 if unable to give exact change
}

// Example usage
let coins = [1, 3, 4]
let amount = 6
let result = minCoins(coins: coins, amount: amount)
print("Minimum number of coins: \(result)")
            

The above code solves the problem by sorting the given types of coins in ascending order and then deducting from the amount using as many of the largest coins as possible while counting the number of coins used.

Result Analysis

The time complexity of this algorithm is O(n log n). (n is the number of coin types) This problem is a typical example of the greedy algorithm, which guarantees an optimal solution when the types of coins increase monotonically or follow a specific pattern.

However, the greedy algorithm does not guarantee an optimal solution in all situations, so caution is needed. For example, while it can find an optimal solution with coin types {1, 3, 4}, the result may change if the types of coins are extended to {1, 3, 4, 6}.