Question Name:THE COIN EXCHANGE PROBLEM

#include<bits/stdc++.h>
using namespace std;
 
long long int getWays(vector<long long int>coins, long long int n, long long int m)
{
    long long int dp[m][n+1], p;
    for(int j=1;j<=n;j++)
    {
        if(j==coins[j]||(j%coins[0])==0)
        dp[0][j] = 1;
        else
        dp[0][j] = 0;
    }
    for(int i=1;i<m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(coins[i]>=j)
            {
              dp[i][j] = dp[i-1][j];
              if(coins[i] == j)
               dp[i][j]+= 1;
            }
            else
            {
                if(j>=(coins[i]*2))
                {
                    dp[i][j] = dp[i-1][j]+dp[i][(j-coins[i])];
                }
                else {
                    dp[i][j] = dp[i-1][j]+dp[i-1][(j-coins[i])];
                    p = (j%coins[i])?0:1;
                    dp[i][j]+=p;
                    }
            }
        }
    }
    
    return dp[m-1][n];
}
int main()
{
        long long int n,m,i;
        scanf("%lld%lld",&n,&m);
        vector<long long int>coins(m);
        for(i=0;i<m;i++)
        {
            scanf("%lld",&coins[i]);
        }
    if(n==0)
        cout<<0;
    else {
        cout<<getWays(coins, n, m);
        }
    return 0;
}
  • Problem Description
    How many different ways can you make change for an amount, given a list of coins? In this problem, your code will need to efficiently compute the answer.

    Task

    Write a program that, given

    1.The amount N to make change for and the number of types M of infinitely available coins
    2. A list of M coins – C={C1, C2, C3,…,CM} 
    Prints out how many different ways you can make change from the coins to STDOUT. 

    Input Format

    First line will contain 2 integer N and M respectively. 
    Second line contain M integer that represent list of distinct coins that are available in infinite amount.

    Constraints
    1<=Ci<=50 
    1<=N<=250 
    1<=M<=50

    The list of coins will contain distinct integers.

    Output Format
    One integer which is the number of ways in which we can get a sum of N from the given infinite supply of M types of coins.
  • Test Case 1
    Input (stdin)4 3
    1 2 3
    Expected Output4
  • Test Case 2
    Input (stdin)10 4
    2 5 3 6
    Expected Output5

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.