Coin Change Greedy Algorithm Not Passing Test Case

Question

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;
    }
}

Answer 1

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.