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.

Powered By
CHP Adblock Detector Plugin | Codehelppro