Problem 41: Coin Change Problem

Problem Statement: Given a list of coin denominations and a target sum, compute the minimum number of coins required to make up that sum. If it is not possible, output -1.

Input

The first line contains two integers n and target, where n is the number of coin denominations. The second line contains n space-separated integers representing the coin values.

Output

Print the minimum number of coins required to obtain the target sum, or -1 if not possible.

Examples


Input:
3 11
1 2 5

Output:
3

Solution Explanation

Method 1: Use dynamic programming where dp[i] represents the minimum coins needed for sum i; update the dp array for each coin. Method 2: Use a breadth-first search (BFS) on the state space of sums which can work but is less efficient than DP when the target is large.

Solution in C++


#include 
#include 
#include 
using namespace std;

const int INF = 1e9;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, target; cin >> n >> target;
    vector coins(n);
    for(int i = 0; i < n; i++) cin >> coins[i];
    
    vector dp(target + 1, INF);
    dp[0] = 0;
    
    for(int i = 1; i <= target; i++){
        for(int coin : coins){
            if(i - coin >= 0)
                dp[i] = min(dp[i], dp[i-coin] + 1);
        }
    }
    
    cout << (dp[target] == INF ? -1 : dp[target]) << "
";
    return 0;
}