Challenge: Fewest Coins

Lab Java Intermediate 20 points

Given coin values (unlimited coins of each), print the fewest coins that make the amount exactly, or -1 if it can't be made.

Input

Line 1: k amount (amount ≤ 10⁴). Line 2: k coin values.

Output

The fewest coins, or -1.

Example

Input

3 6
1 3 4

Output

Sample input available Sample output available

Editor

Java

Hints

dp[a] = fewest coins for amount a; dp[0] = 0, everything else starts as “impossible”.

For each amount and each coin c ≤ a: dp[a] = min(dp[a], dp[a - c] + 1).

Solution explanation

O(amount × k). Unlike greedy, DP tries every “last coin”, so it can't be fooled by coins like 1, 3, 4.

Show solution

import java.util.Arrays;
import java.util.Scanner;

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

Output

Answer