---

Mastering the Change-Making Problem in Crystal: The Ultimate Guide

The change-making problem is a classic computer science puzzle solved efficiently in Crystal using a greedy algorithm. This method involves iteratively selecting the largest available coin denomination that is less than or equal to the remaining target amount, repeating the process until the amount reaches zero, which is optimal for standard coin systems.

Have you ever stood at a checkout counter, handed over a large bill for a small purchase, and watched the cashier almost instantly figure out the exact combination of bills and coins to give back? This seemingly simple task is a real-world manifestation of a fundamental problem in computer science: the change-making problem. It’s a puzzle that appears simple on the surface but hides layers of algorithmic complexity and optimization challenges.

Many developers, both new and experienced, encounter this problem in technical interviews or as part of algorithmic training. The pressure is on to not just find a solution, but to find an efficient one. You might be wondering how to approach this logically, how to write clean and effective code, and what pitfalls to avoid. This guide is your answer. We will deconstruct the change-making problem from the ground up, providing a complete, production-ready solution in the elegant Crystal language, exclusively from the kodikra.com learning curriculum.

---

What Exactly Is the Change-Making Problem?

At its core, the change-making problem asks a straightforward question: Given a set of available coin denominations and a target amount, what is the minimum number of coins required to make that exact amount? This is an optimization problem, where the goal is to minimize the quantity of coins returned.

For instance, if you need to provide 40 cents in change and you have pennies (1), nickels (5), dimes (10), and quarters (25), the optimal solution is one quarter, one dime, and one nickel (3 coins), not four dimes (4 coins) or 40 pennies (40 coins). The human brain often solves this "greedily" by picking the largest possible coin first, and for most real-world currency systems, this works perfectly.

In computer science, this problem serves as a perfect introduction to several key concepts:

• Greedy Algorithms: A strategy that makes the locally optimal choice at each step with the hope of finding a global optimum.
• Dynamic Programming: A more robust (but complex) method that breaks the problem down into smaller subproblems to guarantee an optimal solution for any coin system.
- Computational Complexity: Analyzing how the efficiency of an algorithm scales with the size of the input (the number of coins and the target amount).

Understanding how to solve this problem demonstrates a solid grasp of algorithmic thinking, which is a critical skill for any software engineer. It's a foundational challenge featured in our exclusive Crystal programming guides that builds the logic needed for more advanced tasks.

---

Why This Problem is a Gateway to Advanced Algorithms

The change-making problem isn't just an academic exercise; it's a practical puzzle that models resource allocation challenges found across the tech industry. Think about a CDN (Content Delivery Network) deciding which server sizes to provision to meet traffic demands, or a financial system calculating trade settlements with minimal transactions. The underlying logic is surprisingly similar.

The primary reason this problem is so valuable in a learning context is its perfect illustration of the Greedy Algorithm strategy. A greedy algorithm builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. It's like climbing a hill by always taking the steepest path upwards—you hope it leads you to the highest peak, not just a local maximum.

For standard "canonical" coin systems (like USD or EUR), the greedy approach is not only fast but also correct. A coin system is canonical if the greedy algorithm yields the optimal solution for any target amount. However, the true learning moment comes when you realize this approach can fail. If you had coins of values [1, 6, 10] and needed to make change for 12, a greedy algorithm would choose 10 + 1 + 1 (3 coins), whereas the optimal solution is 6 + 6 (2 coins). This limitation is what pushes developers to learn more powerful techniques like Dynamic Programming.

---

How to Solve the Change-Making Problem in Crystal: A Greedy Approach

For this module from the kodikra curriculum, we'll focus on the greedy approach, as it's the most intuitive and efficient solution for canonical coin systems. The logic is simple: always subtract the largest possible coin from the remaining amount until you reach zero.

Our strategy will be:

1. Handle edge cases first: a negative target amount is impossible, and a target of zero requires no coins.
2. Sort the available coins in descending order to easily access the largest denominations.
3. Iterate through the sorted coins. For each coin, use it as many times as possible without exceeding the remaining target amount.
4. Subtract the value of the chosen coin from the remaining amount and add it to our result list.
5. If, after checking all coins, the remaining amount is still greater than zero, it means the change cannot be made with the given denominations.
6. Finally, return the list of coins used, typically sorted in ascending order for consistency.

The ASCII Logic Flow

Here is a visual representation of our greedy algorithm's logic flow. It illustrates the decision-making process at each step as we work to reduce the target amount to zero.

    ● Start
    │
    ▼
  ┌────────────────────────┐
  │ Get Target & Coin List │
  └───────────┬────────────┘
              │
              ▼
    ◆ Target < 0 ? ─── Yes ──> [Throw NegativeTargetError]
    │
    No
    │
    ▼
    ◆ Target == 0 ? ─── Yes ──> [Return Empty List]
    │
    No
    │
    ▼
  ┌────────────────────────┐
  │ Sort Coins Descending  │
  └───────────┬────────────┘
              │
              ▼
  ┌─ Loop through each coin ┐
  │           │            │
  │           ▼            │
  │   while remaining ≥ coin
  │      ├─ Add coin to result
  │      └─ remaining -= coin
  │                          │
  └───────────┬────────────┘
              │
              ▼
    ◆ remaining > 0 ? ── Yes ──> [Throw ImpossibleCombinationError]
    │
    No
    │
    ▼
  ┌────────────────────────┐
  │ Sort Result Ascending  │
  └───────────┬────────────┘
              │
              ▼
           ● End

The Complete Crystal Solution

Here is the full, commented source code in Crystal. We define a module Change containing our logic and two custom error classes for clear and explicit error handling. This structure promotes modularity and makes the code easy to test and integrate.

# The Change module encapsulates the logic for solving the change-making problem.
# It provides a single public method, `generate`, to compute the result.
module Change
  # Custom error raised when the target amount cannot be formed
  # by any combination of the given coins.
  class ImpossibleCombinationError < StandardError
  end

  # Custom error raised when the target amount is negative,
  # which is an invalid input for this problem.
  class NegativeTargetError < StandardError
  end

  # Generates the fewest number of coins that sum up to the target amount.
  #
  # This implementation uses a greedy algorithm, which is optimal for
  # canonical coin systems (like USD, EUR, etc.).
  #
  # Arguments:
  # - coins: An array of available coin denominations (e.g., [1, 5, 10, 25]).
  # - target: The total amount for which to make change.
  #
  # Returns:
  # - An array of coins that sum to the target, sorted in ascending order.
  #
  # Raises:
  # - NegativeTargetError if the target is less than 0.
  # - ImpossibleCombinationError if the target cannot be met with the given coins.
  def self.generate(coins : Array(Int32), target : Int32) : Array(Int32)
    # --- 1. Handle Edge Cases ---
    # A negative target is a logical impossibility for making change.
    raise NegativeTargetError.new("Target cannot be negative") if target < 0

    # A target of 0 is already met, so no coins are needed.
    return [] of Int32 if target == 0

    # --- 2. Prepare for Greedy Selection ---
    # Sorting coins from largest to smallest is the core of the greedy strategy.
    # This ensures we always try the largest possible coin first.
    sorted_coins = coins.sort.reverse

    # --- 3. Main Greedy Loop ---
    result = [] of Int32
    remaining_amount = target

    sorted_coins.each do |coin|
      # For the current coin, use it as many times as possible.
      while remaining_amount >= coin
        result << coin
        remaining_amount -= coin
      end
    end

    # --- 4. Verify the Result ---
    # If remaining_amount is not zero, it means we couldn't make exact change.
    # For example, trying to make change for 3 with coins [2, 5].
    if remaining_amount > 0
      raise ImpossibleCombinationError.new("Cannot make change for the given target")
    end

    # --- 5. Return the Final Result ---
    # Sorting the result is a common convention for consistency in output.
    result.sort
  end
end

Code Walkthrough and Explanation

Let's break down the Crystal code step-by-step to understand how it achieves the goal.

1. Module and Custom Errors: We define a module Change to namespace our code. Inside, we declare two custom error classes, ImpossibleCombinationError and NegativeTargetError. Using custom errors is a best practice because it allows calling code to rescue specific failure scenarios gracefully, rather than catching a generic StandardError.
2. Input Validation: The first two lines inside the generate method are guards. raise NegativeTargetError.new if target < 0 immediately stops execution for invalid input. return [] of Int32 if target == 0 handles the trivial base case where no work is needed. This makes the rest of the algorithm simpler.
3. Sorting for Greed: The line sorted_coins = coins.sort.reverse is the heart of the greedy preparation. By sorting the coins in descending order, our subsequent loop can be confident that the first coin it considers is always the largest denomination available.
4. Initialization: We initialize an empty array result to store the coins we select and a variable remaining_amount to keep track of how much value we still need to make up.
5. The Core Loop: The sorted_coins.each do |coin| ... end block iterates through our denominations from largest to smallest. The inner while remaining_amount >= coin loop is where the "greedy" choice happens. It repeatedly uses the current coin as long as it "fits" into the remaining amount, adding it to the result and decrementing the remaining_amount each time.
6. Final Check: After the loops complete, we must verify our success. The if remaining_amount > 0 check is crucial. If the value is non-zero, it means the provided coin set was insufficient to make the target amount (e.g., target 7 with coins [2, 4]). In this case, we raise ImpossibleCombinationError.
7. Return Value: If we successfully reach a remaining_amount of 0, we return the result.sort. Sorting the final list ascendingly is a conventional requirement to ensure the output is predictable and easy to verify.

Running the Code

To test this solution, save the code as a file (e.g., change.cr). You can then use Crystal's interactive runner (crystal i) or create a separate test file. Here’s how you could run it from a simple script:

# Save the module code in change.cr
# Create a new file, e.g., run.cr

# run.cr
require "./change"

target = 40
coins = [1, 5, 10, 25, 100]

begin
  result = Change.generate(coins, target)
  puts "Change for #{target} is: #{result}"
rescue Change::ImpossibleCombinationError => e
  puts "Error: #{e.message}"
rescue Change::NegativeTargetError => e
  puts "Error: #{e.message}"
end

Now, execute the script from your terminal:

$ crystal run run.cr
Change for 40 is: [5, 10, 25]

---

Where the Greedy Approach Fails: Non-Canonical Coin Systems

For all its elegance and speed, the greedy algorithm has a critical weakness: it only guarantees an optimal solution for canonical coin systems. A non-canonical system is one where the greedy choice does not lead to the fewest number of coins.

This is a vital concept to understand because it highlights that the most obvious algorithm is not always the correct one. It forces us to think more deeply about the problem's constraints.

Example of Failure:

• Coin System: [1, 6, 10]
• Target Amount: 12

Let's trace our greedy algorithm's logic with this input:

    ● Start: Target = 12, Coins = [10, 6, 1]
    │
    ▼
  ┌────────────────────────┐
  │ remaining = 12         │
  │ result = []            │
  └───────────┬────────────┘
              │
              ▼
    ◆ Try coin 10: 12 ≥ 10? Yes.
    │  ├─ result = [10]
    │  └─ remaining = 12 - 10 = 2
    │
    ▼
    ◆ Try coin 6: 2 ≥ 6? No.
    │
    ▼
    ◆ Try coin 1: 2 ≥ 1? Yes.
    │  ├─ result = [10, 1]
    │  └─ remaining = 2 - 1 = 1
    │
    ▼
    ◆ Try coin 1 again: 1 ≥ 1? Yes.
    │  ├─ result = [10, 1, 1]
    │  └─ remaining = 1 - 1 = 0
    │
    ▼
  ┌────────────────────────┐
  │ Greedy Solution: [10, 1, 1] │
  │ Coin Count: 3          │
  └────────────────────────┘

The greedy algorithm returns [10, 1, 1], for a total of 3 coins. However, the truly optimal solution is [6, 6], which uses only 2 coins. The greedy choice to take the 10-cent coin first prevented it from discovering the better combination of two 6-cent coins.

When to Use Greedy vs. A More Robust Approach

This distinction leads to a critical decision point in software design. When should you use a simple greedy algorithm versus a more complex but always-correct method like dynamic programming?

Factor	Greedy Algorithm	Dynamic Programming
Speed	Extremely fast. Complexity is roughly O(N log N) due to sorting, where N is the number of coin types.	Slower. Complexity is O(N * T), where N is the number of coin types and T is the target amount.
Correctness	Guaranteed optimal only for canonical coin systems.	Guaranteed optimal for any coin system.
Implementation Complexity	Simple and intuitive to write and understand.	More complex, requires understanding of memoization or tabulation to build up solutions to subproblems.
Use Case	Ideal for problems with known canonical inputs, like real-world currency calculations, where performance is critical.	Necessary for problems where the input system is arbitrary or non-canonical, and optimality is a strict requirement.

For the scope of the kodikra module and most interview scenarios involving standard currency, the greedy solution is often what's expected. However, acknowledging its limitations and being able to discuss the alternative (dynamic programming) demonstrates a deeper level of understanding.

---

Frequently Asked Questions (FAQ)

1. Why do we need to sort the coins in descending order?

Sorting the coins from largest to smallest is the fundamental principle of the greedy strategy. It ensures that at every step of the algorithm, we are considering the largest possible denomination that can be used. This "greedy choice" is what makes the algorithm simple and fast, as it attempts to reduce the remaining amount as quickly as possible.

2. What happens if the `coins` array contains a zero or negative numbers?

Our current implementation doesn't explicitly handle this, but a robust solution should. If the array contained a zero, it could lead to an infinite loop if the target is not zero. Negative coin values don't make logical sense in this problem context. A production-grade version would add input validation to filter out non-positive coin values before processing.

3. How does this algorithm's performance scale?

The performance is dominated by the initial sort, which is O(N log N), where N is the number of coin denominations. The subsequent looping is proportional to the target amount (T) in the worst case, but on average, it's much faster. For practical purposes, it's highly efficient. This is much better than the O(N * T) complexity of a typical dynamic programming solution.

4. Is there a way to check if a coin system is canonical?

Yes, there are mathematical tests to determine if a coin system is canonical, but they are quite complex and beyond the scope of this introduction. For practical purposes, if the problem involves standard, real-world currency, you can safely assume it's canonical and that a greedy approach will work.

5. Why use custom error classes like `ImpossibleCombinationError`?

Using specific, custom error classes is a software engineering best practice. It makes the code that calls our `Change.generate` method more robust. The calling code can use a `rescue` block to specifically catch `ImpossibleCombinationError` and handle it differently from a `NegativeTargetError` or any other potential runtime error. It makes the program's error-handling logic more precise and readable.

6. Could this be solved recursively?

Absolutely. A recursive solution is a natural way to think about this problem. A recursive greedy function would find the largest coin smaller than the target, and then call itself with the new target (target - coin). However, an iterative solution with a loop, like the one we've implemented, is often more efficient in Crystal as it avoids the overhead of repeated function calls and potential stack overflow for very large targets.

---

Conclusion: From Theory to Practical Mastery

We've journeyed from a simple real-world scenario—making change—to a deep, practical implementation in Crystal. You now understand not just how to solve the change-making problem using a greedy algorithm, but also why it works and, crucially, when it might not. This nuanced understanding is what separates a novice programmer from an expert problem-solver.

The key takeaways are clear: the greedy algorithm is a powerful, fast, and elegant solution for canonical coin systems. Its implementation in Crystal is straightforward, leveraging sorting and simple loops to achieve an efficient result. By also understanding its limitations and the existence of more robust solutions like dynamic programming, you are well-equipped to tackle a wide range of optimization problems.

This problem is a stepping stone. As you continue through the Kodikra Crystal learning path, you'll find that the principles of algorithmic thinking, edge case handling, and choosing the right tool for the job will reappear in more complex and challenging modules.

Disclaimer: The code in this article is written for Crystal 1.12+ and is expected to be compatible with future versions. The logic and principles discussed are timeless and apply broadly across programming languages.

---

Published by Kodikra — Your trusted Crystal learning resource.