Find the Minimum Number of Coins for an Amount

Question

The candidate is asked to determine the minimum number of coins required to make a specific amount using given denominations of coins.

Codemia · Accepted Answer

To solve the problem of finding the minimum number of coins for a given amount, we can use a dynamic programming approach. The idea is to build an array `dp` where `dp[i]` represents the minimum number of coins needed to make the amount `i`. We initialize `dp[0]` to 0 (as no coins are needed to make the amount 0) and all other entries to a large value (infinity) to represent that those amounts are initially unreachable.

1. Initialize the `dp` array with size `amount + 1` and set `dp[0] = 0`.
2. For each coin in the denominations, iterate through all amounts from the coin value to the target amount.
3. For each amount `i`, update `dp[i]` as follows:
   - `dp[i] = min(dp[i], dp[i - coin] + 1)` if `i - coin >= 0`.
4. After processing all coins, check `dp[amount]`. If it is still infinity, return -1, indicating that the amount cannot be formed with the given coins.

The time complexity of this algorithm is O(n * m), where `n` is the amount and `m` is the number of coin denominations. The space complexity is O(n) due to the `dp` array. This approach is efficient for moderate values of `n` and `m`, and it effectively handles various combinations of coins.

```python
def min_coins(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

# Example usage:
coins = [1, 2, 5]
amount = 11
print(min_coins(coins, amount))  # Output: 3 (11 = 5 + 5 + 1)
```

It is important to consider edge cases such as when the amount is 0 (should return 0), or when no combination of coins can form the amount (should return -1). Additionally, if the coin denominations are larger than the amount, the function should handle this gracefully.

Find the Minimum Number of Coins for an Amount

Pinterest

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Approach

Algorithm

Submit Your Answer

Pinterest Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string