Practice/Amazon/Leetcode 322. Coin Change

Leetcode 322. Coin Change

CodingMust

Problem

You are given an array of coin denominations and a target amount. Each denomination can be used an unlimited number of times. Your task is to determine the minimum number of coins required to make up the target amount.

If it is impossible to form the target amount using any combination of the given coins, return -1.

Requirements

1. Calculate the fewest coins needed to reach the exact target amount
2. Each coin denomination can be used multiple times
3. Return -1 if the amount cannot be formed
4. Return 0 if the target amount is 0

Constraints

• 1 ≤ coins.length ≤ 12
• 1 ≤ coins[i] ≤ 2^31 - 1
• 0 ≤ amount ≤ 10^4
• All coin denominations are distinct positive integers

Examples

Example 1:

Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: Use three coins: 5 + 5 + 1 = 11

Example 2:

Input: coins = [2], amount = 3 Output: -1 Explanation: Cannot form 3 using only coins of value 2

Example 3:

Input: coins = [1], amount = 0 Output: 0 Explanation: No coins needed to make 0

Example 4:

Input: coins = [1, 3, 4, 5], amount = 13 Output: 3 Explanation: Use three coins: 5 + 4 + 4 = 13 (better than 5 + 5 + 3)