CODEWITHSUNDEEP
algorithmdynamic-programminggreedycoin-change
j.Doie
j.Doie

Reputation: 91

Coin Change Greedy Algorithm Not Passing Test Case

I'm trying to solve the coin change problem where you use the fewest amounts of coins possible to make an amount. I'm trying to use the Greedy Approach - my algorithm sorts the coins array, starts with the biggest coin and uses it as many times as possible before moving on the next coin that will divide the remainder.

This worked for the initial test case:

coins = [1,2,5], amount = 11

But failed for this one:

coins = [186,419,83,408], amount = 6249

I'm not sure why it's failing, I'm still trying to grasp the greedy approach. Would really appreciate any feedback!

class Solution {
    public int coinChange(int[] coins, int amount) {
        int count = 0;
        
        if(coins.length == 1 && amount % coins[0] != 0) {
            return -1;
        }

        Arrays.sort(coins);
        
        int i = coins.length - 1;
        while(amount >= 0 && i >= 0) {
             if(coins[i] <= amount) {
                int remainder = amount / coins[i];
                    count = count + remainder;
                    amount -= (remainder * coins[i]);
            }
            i--;
        }
    
        return count;
    }
}

Upvotes: 0

Views: 1095

Answers (1)

Eloy P&#233;rez Torres
Eloy P&#233;rez Torres

Reputation: 1177

Greedy approach to coin change problem doesn't work on the general case (arbitrary coin values).
Example:
Coins = [2, 3, 6, 7] and Amount = 12,
Greedy takes [2, 3, 7] and the optimal choice is [6, 6].

You need to use the dynamic programming approach to have the optimal value.

Upvotes: 3

Related Questions