algoadvance

You are given an integer array coins representing coins of different denominations and an integer amount representing a total amount of money.

Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

You may assume that you have an infinite number of each kind of coin.

Example

  1. Example 1:
    • Input: coins = [1, 2, 5], amount = 11
    • Output: 3 (Explanation: 11 = 5 + 5 + 1)
  2. Example 2:
    • Input: coins = [2], amount = 3
    • Output: -1 (Explanation: No combination can form 3 with coin 2)
  3. Example 3:
    • Input: coins = [1], amount = 0
    • Output: 0 (Explanation: 0 coins needed to make 0 amount)
  4. Example 4:
    • Input: coins = [1], amount = 2
    • Output: 2 (Explanation: 1+1=2, so minimum coins = 2)

Constraints:

Clarifying Questions

  1. Does the order of coins matter? No, the order does not matter.

  2. Can the same denomination be used multiple times? Yes, you can use an unlimited number of coins of each denomination.

  3. What should be returned if the amount is 0? Return 0 since no coins are needed to make an amount of 0.

  4. Can the coins array be empty? No, based on the constraints (1 <= coins.length).

Strategy

  1. Dynamic Programming Approach:
    • Use a list dp where dp[i] will store the minimum number of coins needed to make the amount i.
    • Initialize:
      • dp[0] = 0 because 0 coins are needed for amount 0.
      • dp[i] for i from 1 to amount should be set to infinity (float('inf')), indicating that initially, it is assumed to be impossible to form that amount.
    • Iterate over each coin and update the dp list as:
      • For each coin c and for each amount i from c to amount, update dp[i] with the formula: dp[i] = min(dp[i], dp[i - c] + 1)
    • Finally, dp[amount] will have our answer. If it remains infinity, return -1.

Code

def coinChange(coins, amount):
    # Initialize the dp array with infinity for all indexes except dp[0]
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    
    # Update the dp table
    for coin in coins:
        for i in range(coin, amount + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)
    
    # If dp[amount] is still infinity, we weren't able to form 'amount'
    return dp[amount] if dp[amount] != float('inf') else -1

# Example usage
print(coinChange([1, 2, 5], 11))  # Output: 3
print(coinChange([2], 3))         # Output: -1
print(coinChange([1], 0))         # Output: 0
print(coinChange([1], 2))         # Output: 2

Time Complexity

The time complexity of the algorithm is O(n * m), where n is the length of the coins array and m is the amount.

This ensures that the solution is computationally feasible for the given constraints.

Try our interview co-pilot at AlgoAdvance.com