We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. The Coin Change Problem
  2. Discussions

The Coin Change Problem

Sort by

recency

|

25 Discussions

|

  • trunglaitruly
     + 0 comments

    Python, top down

    def getWaysHelper(target, index, coins, solved):
    if index == len(coins) or target < 0:
        return 0
    if target == 0:
        return 1
    if (target, index) in solved:
        return solved[(target, index)]
    
    curcoin = coins[index]
    p1 = getWaysHelper(target-curcoin, index, coins, solved)
    p2 = getWaysHelper(target, index+1, coins, solved)

    solved[(target, index)] = p1 + p2
    return p1 + p2

def getWays(n, c):
    solutiontable = dict()
    return getWaysHelper(target=n, index=0, coins=c, solved=solutiontable)

  • Chengpu2
     + 1 comment

    I wonder if the official answers are correct. For the run case getWays(4, [1,2,3]), my answer is 2 ({2, 2} and {1, 3}), but the official answer is 4. For the run case getWays(10, [2,5,3,6]), my answer is 12 but the official answer is 5.

  • omkpatel110
     + 0 comments

    include

    include

    using namespace std;

    vector coinChangeGreedy(const vector& coins, int amount) { vector result(coins.size(),0); for(int i=coins.size()-1;i>=0;i--) { result[i] = amount/coins[i]; amount %= coins[i]; } return result; }

    int main() { vector coins = {1,5,10,25}; int amount =47;

    cout<<"Greedy Approach result :"<<endl;
vector <int> resultgreedy = coinChangeGreedy(coins,amount);

for(int i=0;i<resultgreedy.size();i++)
{
    cout<<resultgreedy[i]<<" ";
}
cout<< endl;
return 0;

    }

  • vadym_usatiuk
     + 0 comments

    Java O(n*m)

    public static long getWays(int n, List<Long> c) {
        long[] ways = new long[n + 1];
        ways[0] = 1;

        for (long coin : c) {
            for (int i = (int) coin; i <= n; i++) {
                ways[i] += ways[i - (int) coin];
            }
        }

        return ways[n];
    }

  • muxammadnazar_k1
     + 0 comments
    function getWays(n, c) {
// Initialize an array called 'ways' of length 'n + 1' and fill it with 0s.
let ways = new Array(n + 1).fill(0);
// Set the number of ways to make change for the amount 0 to 1.
ways[0] = 1;

// Iterate through each coin denomination in the array 'c'.
for (let coin of c) {
		// For each coin denomination, iterate through each amount from 'coin' to 'n'.
		for (let amount = coin; amount <= n; amount++) {
				// Update the number of ways to make change for the current 'amount'
				// by adding the number of ways to make change for 'amount - coin'
				// (i.e., the current amount minus the current coin denomination).
				ways[amount] += ways[amount - coin];
		}
}

// Return the number of ways to make change for the target amount 'n'.
return ways[n];
}