Coin Change — Minimum Coins

Practice this coding question on Coding Gurukul.

Problem statement

Given coin denominations and a target amount, find the minimum number of coins needed to make exactly that amount. You may use each denomination any number of times. Print -1 if the amount cannot be made. A target of 0 needs 0 coins. Repeated denominations do not change the answer. Use dynamic programming in O(n*target) time and O(target) space. Choosing the largest coin first is not always optimal. Worked example For coins [1, 3, 4] and target 6, use 3+3. The answer is 2. Using 4+1+1 would require 3 coins.

Input format

First line: n target. Second line: n denominations.

Output format

Print the minimum coin count, or -1.

Constraints

1 <= n <= 100; 0 <= target <= 10000; 1 <= denomination <= 10000.

Sample input

3 6
1 3 4

Sample output

2

Sign in to run or submit a solution in C++, Java or Python.