Coin Change - Java Fail to pass example 3

Question

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.

Lets say you have 3 and 5 in the coins array. And amount is 6 then you will always choose 5 first, after that amount is 1. Use a recursive function and try to backtrack — Akshay Batra, Jan 10 '19 at 04:15
Possible duplicate of [Why does the greedy coin change algorithm not work for some coin sets?](https://stackoverflow.com/questions/13557979/why-does-the-greedy-coin-change-algorithm-not-work-for-some-coin-sets) — Pham Trung, Jan 10 '19 at 04:23

MBo · Accepted Answer · 2019-01-10T04:37:44.423

5

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;

edited Jan 10 '19 at 04:37

answered Jan 10 '19 at 04:13

MBo

77,366
5
53
86

But I sort the denomination at first. So now they have a order not the arbitrary one. – Encipher Jan 10 '19 at 04:16
how sorting helps in this case? @Encipher? – Pham Trung Jan 10 '19 at 04:17
After sorting maximum denomination taken first then the rest of amount adjusted with 2nd maximum denomination. – Encipher Jan 10 '19 at 04:19
@Encipher so, [3,3,4] and 6, after first iteration, you get [3,3] and 2 -> then? – Pham Trung Jan 10 '19 at 04:20
@Encipher Greedy+ Sorting does work for some sets, for example, powers of two, for coin system in most countries, but fails in general case. Look at my example. Choosing `4` blocks the way to the best answer `3+3` – MBo Jan 10 '19 at 04:21
hmm, That's the problem. – Encipher Jan 10 '19 at 04:21
@Encipher amount, will change. Also corrected loop direction to `i--` – MBo Jan 10 '19 at 04:23
c is coin nominal, so it has values `1,2,5 for your example – MBo Jan 10 '19 at 04:28

Coin Change - Java Fail to pass example 3

1 Answers1