CODEWITHSUNDEEP
javaalgorithmwhile-loopdynamic-programmingbrute-force
Encipher
Encipher

Reputation: 2846

Coin Change - Java Fail to pass example 3

Problem: You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11 Output: 3 Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = 2, amount = 3 Output: -1

You may assume that you have an infinite number of each kind of coin.

My code:

public int coinChange(int[] coins, int amount) {
    Arrays.sort(coins);
    int new_amount=amount;
    int count_coin=0;
    int q=0,r=0,a=0;
    int k=coins.length-1;


    while(amount>0 && k>=0) {

            q = new_amount / coins[k];
            count_coin = count_coin + q;
            r = new_amount % coins[k];
            new_amount=r;
            a+=q*coins[k];
            k--;



    }


    if(a==amount){
        return count_coin;
    }
    else{
        return -1;
    } }

My code work well for given two example. After working with this example I took another test case.

Example 3:Input: coins = [186,419,83,408], amount = 6249 Output: 20 My output: -1

I fail to understand this example. If any one have any idea about this example or any other better algorithm besides mine please share it with me.

I see Coin Change (Dynamic Programming) link. But cannot understand.

I also studied Why does the greedy coin change algorithm not work for some coin sets? but cannot understand what does it try to say.So I raised this question.

Thank you in advance.

Upvotes: 0

Views: 728

Answers (1)

MBo
MBo

Reputation: 80107

Your code uses greedy approach that does not work properly for arbitrary coin nominals (for example, set 3,3,4 cannot produce answer 6)

Instead use dynamic programming approach (example)

For example, make array A of length amount+1, fill it with zeros, make A[0] = 1 and traverse array for every coin nominal from n-th entry down, choosing the best result for every cell.

Pseudocode:

 for (j=0; j < coins.length; j++) {
     c = coins[j];
     for (i=amount; i >= c; i--){
          if (A[i - c] > 0)
              A[i] = Min(A[i], A[i - c] + 1);
     }
 }
 result = A[amount] - 1;

Upvotes: 5

Related Questions