Author: [Author Name]
Written on: [Written Date]
Problem Description
This is a problem of calculating the minimum number of coins needed to make change. You need to find a way to make the total amount using the minimum number of coins based on the given denominations and total amount. Assume that there are an infinite number of each type of coin.
For example, if you have coin denominations of {1, 5, 10, 25} and the total amount to be made is 63, you need to determine the minimum number of coins required.
Input
- coinValues: An integer array representing the types of coins (e.g., [1, 5, 10, 25])
- amount: An integer representing the total amount (e.g., 63)
Output
- Returns the minimum number of coins. If it is not possible to make the amount, return -1.
Problem Approach
This problem can be solved using dynamic programming. Dynamic programming involves breaking the problem down into smaller subproblems and combining the solutions to these subproblems to find the solution to the overall problem. To solve this problem, we will follow these steps.
- Initialize the DP table: Create a DP table to record the minimum number of coins needed for each amount that can be made using the coins.
- Set base case: The 0th index of the DP table (0 dollars) does not require any coins, so it is set to 0.
- Utilize previous results: For each coin, calculate the possible amounts and update the DP table.
- Return result: The lowest number of coins to make the required amount, or -1 if it’s impossible.
JavaScript Code Implementation
function coinChange(coinValues, amount) {
// Initialize DP Table
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0; // The number of coins to make 0 dollars is 0
// Check each coin one by one
for (let coin of coinValues) {
for (let j = coin; j <= amount; j++) {
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
}
}
// Return result
return dp[amount] === Infinity ? -1 : dp[amount];
}
This code creates a DP table using the given coinValues array and amount, then calculates the minimum number of coins required.
Description of Process
The above code consists of several steps, which we will explore to minimize the number of coins.
Step 1: Initialize DP Table
const dp = Array(amount + 1).fill(Infinity); This line creates an array of a fixed length and initializes all values to infinity.
Then, dp[0] = 0; sets the number of coins needed to make 0 dollars to 0.
Step 2: Update Amount for Each Coin
for (let coin of coinValues) iterates through each coin to calculate the possible amounts.
In the nested for loop, dp[j] = Math.min(dp[j], dp[j - coin] + 1); updates the minimum number of coins for each amount.
Step 3: Return Result
Finally, return dp[amount] === Infinity ? -1 : dp[amount]; returns -1 if the amount cannot be made. If it can be made, it returns the minimum number of coins.
Examples and Test Cases
Example 1
Input: coinValues = [1, 5, 10, 25], amount = 63
Output: 6
Explanation: A total of 6 coins are used to make 63: 25, 25, 10, 1, 1, 1.
Example 2
Input: coinValues = [2], amount = 3
Output: -1
Explanation: It is not possible to make 3 using only 2.
Example 3
Input: coinValues = [1], amount = 0
Output: 0
Explanation: No coins are needed to make 0 dollars.
Time Complexity and Space Complexity of This Code
The time complexity of this algorithm is O(n * m), where n is the number of coin types and m is the target amount. The complexity arises because updating and creating the DP table involves O(m) operations repeated for each coin.
The space complexity is O(m) due to the dynamically created DP table for the number of coins.
Conclusion
This article discussed how to solve the problem of finding the minimum number of coins using dynamic programming with JavaScript.
After presenting the problem, we explored various solutions and code implementations in depth.
Such algorithms are frequently encountered in actual interviews, so it is advisable to learn them well.
I hope this helps you in your future coding test preparations!