Swift Coding Test Course, Finding the Minimum Number of Coins

Problem Definition

We will address an algorithm problem that minimizes the number of coins needed to make a given amount
based on the types of coins available. For example, if the types of coins are
[1, 5, 10, 25] and the amount is 7,
the number of coins needed is 3 (5 + 1 + 1).

Input

• An array coins containing the types of coins (in int[] format).
• The target amount amount (of int type).

Output

Returns the minimum number of coins. Returns -1 if it is not possible.

Approach to the Problem

This problem can be approached using Dynamic Programming.
The goal is to repeatedly use coins to create the given amount and find the minimum count.
We utilize the properties of optimal substructure and overlapping subproblems with dynamic programming.

Step 1: Initialize the DP Table

First, create an array dp to store the minimum number of coins for each index i.
Initialize dp[0] to 0 and the rest to infinity.

Step 2: Update the DP Table

Loop through each coin and update the amount that can be made with that coin.
Each amount i is updated from the previous amount i - coin
by adding +1 to the coin count.

Swift Code Implementation

            func minCoins(coins: [Int], amount: Int) -> Int {
                // Initialize the DP table
                var dp = Array(repeating: Int.max, count: amount + 1)
                dp[0] = 0

                // Update the DP table
                for coin in coins {
                    for i in coin...(amount) {
                        if dp[i - coin] != Int.max {
                            dp[i] = min(dp[i], dp[i - coin] + 1)
                        }
                    }
                }

                return dp[amount] == Int.max ? -1 : dp[amount]
            }

            // Example usage
            let coins = [1, 5, 10, 25]
            let amount = 7
            let result = minCoins(coins: coins, amount: amount)
            print("Minimum number of coins: \(result)")
        

Time Complexity Analysis

The time complexity of this algorithm is O(m * n).
Here, m is the number of types of coins, and n is the target amount.
The outer loop iterates over the types of coins, and the inner loop iterates over the target amount,
resulting in two nested loops.

Additional Problems and Variations

This problem can be modified to add various requirements.
For example, there may be variations where only specific coins must be used,
or coins cannot be used multiple times.
It is also important to consider such variations.