Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Dynamic Programming

Coin Change (Minimum Coins)

Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft, Goldman Sachs, Paytm

Using coins of the given denominations (unlimited supply), make the amount with the fewest coins. Print that number, or -1 if it is impossible.

Input

First line: n. Second line: n denominations. Third line: amount.

Output

The minimum number of coins, or -1.

Constraints

Greedy fails for some coin systems — use dp[x] = 1 + min(dp[x − coin]).

Example 1

Input

3
1 2 5
11

Output

3

Example 2

Input

1
2
3

Output

-1

Hints

  1. Greedy (always take the biggest coin) fails: coins {1, 3, 4}, amount 6 → greedy uses 4+1+1, best is 3+3.
  2. dp[x] = fewest coins for amount x = 1 + min(dp[x − c]) over coins c ≤ x, with dp[0] = 0.

Approach

Fill dp[0..amount] from small to large, using "infinity" for unreachable amounts. For each x and each coin c ≤ x, if dp[x − c] is reachable, try dp[x − c] + 1. The answer is dp[amount], or -1 if it's still infinity. Amount 0 needs 0 coins.

Complexity: O(amount · n) time · O(amount) space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, amount;
    cin >> n;
    vector<int> coins(n);
    for (auto &c : coins) cin >> c;
    cin >> amount;
    const int INF = INT_MAX;
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int x = 1; x <= amount; x++)
        for (int c : coins)
            if (c <= x && dp[x - c] != INF) dp[x] = min(dp[x], dp[x - c] + 1);
    cout << (dp[amount] == INF ? -1 : dp[amount]) << "\n";
    return 0;
}

Python solution

import sys

data = list(map(int, sys.stdin.read().split()))
n = data[0]
coins, amount = data[1 : n + 1], data[n + 1]
INF = float("inf")
dp = [0] + [INF] * amount
for x in range(1, amount + 1):
    for c in coins:
        if c <= x and dp[x - c] + 1 < dp[x]:
            dp[x] = dp[x - c] + 1
print(-1 if dp[amount] == INF else dp[amount])

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] coins = new int[n];
        for (int i = 0; i < n; i++) coins[i] = sc.nextInt();
        int amount = sc.nextInt();
        final int INF = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int x = 1; x <= amount; x++)
            for (int c : coins)
                if (c <= x && dp[x - c] != INF) dp[x] = Math.min(dp[x], dp[x - c] + 1);
        System.out.println(dp[amount] == INF ? -1 : dp[amount]);
    }
}

Solve Coin Change (Minimum Coins) online · All practice problems