Class Change

java.lang.Object
topics.greedy.change.Change
public class Change extends Object

Coin Change

Calculates the number of coins required to make a specific amount of change. The heuristic (Greedy Choice) is to always pick the largest possible coin denomination that does not exceed the remaining amount.

The Greedy Trap

While this algorithm is blazingly fast O(C), it does not guarantee the globally optimal solution (minimum number of coins) for all currency systems. It works perfectly for standard currencies (like US Dollars or Euros) which are canonical, but fails on arbitrary coin sets (e.g., coins = {20, 15, 1}, amount = 30. Greedy gives 15 coins: 20x1 + 1x10. Optimal is 2 coins: 15x2).

Financial Software Note

Never use float or double for currency calculations due to IEEE 754 binary precision loss. Always use integers (representing the smallest sub-unit, e.g., cents) or java.math.BigDecimal.

Author:
vicegd

  • Constructor Details

    • Change

      public Change()

  • Method Details

    • calculateCoins

      public int[] calculateCoins(int amount, int[] coins)
      Calculates the change using a purely greedy approach.

      Optimized using Integer Division and Modulo instead of repeated subtraction, making the time complexity strictly bound by the number of coin types.

      • Time Complexity: O(C) where C is the length of the coins array.
      • Space Complexity: O(C) to store the solution array.
      Parameters:
      amount - The target amount to return (must be non-negative).
      coins - The available coin denominations, strictly sorted in descending order.
      Returns:
      An array of the same length as coins, representing the count of each coin used.