Cracking The Coding Interview Together – Problem 8.11: Coins

Have you ever stood at a self-checkout register, dumping a handful of loose change, and wondered just how many unique combinations of coins could equal your total? It sounds like a trivial puzzle for a rainy afternoon, but when we scale this up to financial systems, vending machines, or currency exchange algorithms, getting this wrong leads to massive performance bottlenecks or incorrect transaction processing. Today, we are diving into Problem 8.11 from Cracking the Coding Interview: Coins. Our shared goal is to move past naive recursive explosions and build a production-ready, highly optimized solution using dynamic programming.

Problem Statement

Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents), and pennies (1 cent), write code to calculate the number of ways of representing n cents. We need to design a robust algorithm that accepts an integer amount n and returns the total number of distinct combinations that sum up to n. Order does not matter; for example, a nickel plus five pennies is the exact same combination as six pennies and a nickel, assuming we count coin types rather than specific physical coins.

Analyze the Problem Together

Let's break down the constraints and find the "Aha!" conflict. If we approach this purely using naive recursion, we might try every possible sequence of coins. However, this immediately exposes us to massive redundant calculations. If we choose a dime, we are left with n - 10 cents. If we later arrive at n - 10 via two nickels, we recompute the exact same subproblem. This overlapping subproblem property is the classic signature of dynamic programming.

Let's compare our options:

By leveraging dynamic programming, we can systematically eliminate redundant states. We will build our solution using top-down memoization first to understand the state transitions clearly, and then analyze how we can optimize space.

Questions for the Interviewer

Before we write a single line of code, as senior engineers, we must clarify the boundaries of our problem:

• What are the upper limits for n? Will n fit within a standard 32-bit integer, or should we anticipate large values that require 64-bit longs to prevent integer overflow?
• Can the set of coin denominations change dynamically, or are they strictly fixed to 25, 10, 5, and 1?
• How should the system handle negative or zero values of n?
• Are there memory constraints we need to respect, or can we freely allocate memoization tables?

Think About the Solution

Our solution relies on making a choice for each coin denomination. For a given amount n and a specific coin, we can either use 0 of that coin, 1 of that coin, 2 of that coin, and so on, until the coin value exceeds the remaining amount. Alternatively, we can structure our recursive function to branch into two choices: using one coin of the current denomination (and staying with the same denomination) or moving to the next smaller denomination without using any of the current coin.

This second framing drastically simplifies our state representation to (remainingAmount, coinIndex). We will use a 2D memoization array where rows represent the remaining amount and columns represent the coin index. This prevents duplicate counting of combinations because we strictly process coins in descending order of their value.

Write Code and Explain

Let's look at the production-ready Java implementation:

public class CoinChangeCalculator {

    public static long makeChange(int n) {
        int[] denominators = {25, 10, 5, 1};
        long[][] memo = new long[n + 1][denominators.length];
        // Initialize memoization table with -1
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j < denominators.length; j++) {
                memo[i][j] = -1;
            }
        }
        return makeChangeHelper(n, denominators, 0, memo);
    }

    private static long makeChangeHelper(int amount, int[] denominators, int index, long[][] memo) {
        // Base case 1: Exact match found
        if (amount == 0) {
            return 1;
        }
        
        // Base case 2: Ran out of coins or amount dropped below zero
        if (index >= denominators.length - 1) {
            return 1; // Only 1 way left: using pennies
        }

        // Check if result is already cached
        if (memo[amount][index] != -1) {
            return memo[amount][index];
        }

        int coinAmount = denominators[index];
        long ways = 0;
        
        // Iterate through all possible counts of the current coin
        for (int i = 0; i * coinAmount <= amount; i++) {
            int remainingAmount = amount - (i * coinAmount);
            ways += makeChangeHelper(remainingAmount, denominators, index + 1, memo);
        }

        // Cache and return
        memo[amount][index] = ways;
        return ways;
    }

    public static void main(String[] args) {
        int n = 100;
        System.out.println("Number of ways to make " + n + " cents: " + makeChange(n));
    }
}

Walkthrough of the Code:

1. We define our standard coin denominations in descending order: {25, 10, 5, 1}.
2. We initialize a 2D memoization array memo[n + 1][denominators.length] filled with -1 to track uncomputed states.
3. In our helper method, if the amount reaches 0, we return 1 representing a successful unique combination. If we reach the last coin type (pennies), there is only 1 way to form the remaining amount, so we return 1.
4. We loop through all possible counts of the current coin denomination, subtract their total value from the remaining amount, and recursively call the function for the next coin index.
5. We store the aggregated result in our memo table before returning, ensuring we never calculate the same subproblem twice.

Time & Space Complexity

Let's analyze the resource utilization of our solution:

• Time Complexity: O(n * c), where n is the target amount and c is the number of coin denominations (which is 4 in our case). Because our memoization table has n x c states and each state takes linear time relative to the coin count in the worst case, the total operations scale linearly with the amount.
• Space Complexity: O(n * c) for the memoization table and the recursion call stack. For c = 4, this simplifies to O(n) auxiliary space, making it extremely memory-efficient.

Why This Problem Matters (The Senior Perspective)

Beyond cracking technical interviews, this problem is a foundational archetype for resource allocation, knapsack-variant problems, and dynamic programming optimization. In production systems—such as financial ledger software, billing engines, or distributed inventory management—calculating optimal distributions under constraints is an everyday requirement. Furthermore, understanding how to transition from exponential recursion to memoized tabulation separates junior engineers from seniors who instinctively design for scalability, thread safety, and memory thriftiness.

Final Thoughts

Dynamic programming doesn't have to be intimidating. By breaking problems down into clear recursive choices, identifying overlapping subproblems, and applying memoization, we turn impossible computational walls into elegant solutions. Take this code, refactor it into a bottom-up tabulation approach as an exercise, and see how much memory you can save. Happy coding, and see you in the next breakdown!