Change Maker

Level: Intermediate 30–60 min

Concepts: Algorithms

Solutions: C# | TypeScript | Python

You need to write the software to calculate the minimum number of coins required to return an amount of change to a user of Acme Vending machines. For example, the vending machine has coins 1,2,5 and 10 what is the minimum number of coins required to make up the change of 43 cents?

The coin denominations will be supplied as a parameter. This is so the algorithm is not specific to one country. You may not hardcode these into the algorithm, they must be passed as a parameter.

The country’s denominations to use for the kata are:

  • British Pound
    • 1
    • 2
    • 5
    • 10
    • 20
    • 50
  • US Dollar
    • 1
    • 5
    • 10
    • 25
  • Norwegian Krone
    • 1
    • 5
    • 10
    • 20

The kata assumes an infinite number of coins of each denomination. You are to return an array with each coin to be given as change.

Examples

var coinDenominations = [1,5,10,25]; // coin values converted to whole numbers
var machine = new VendingMachine(coinDenominations);
var purchaseAmount = 1.25; // amount the item cost
var tenderAmount = 2.00; // amount the user input for the purchase
var change = machine.CalculateChange(purchaseAmount, tenderAmount);
 // The expected result would be - (coin denominations as whole numbers)
 // change[0] = 25
 // change[1] = 25
 // change[2] = 25

Bonus

Remove the assumption that there are infinite coins of each denomination. Modify the code to accept a fixed number of each denomination. How will affect the change calculation?

Reference Walkthrough

Reference implementations in C#, TypeScript, and Python live at tddbuddy-reference-katas/change-maker. Eleven scenarios cover zero, single-coin, and multi-coin cases across the three canonical currencies the kata names — US cents (25/10/5/1), British pence (50/20/10/5/2/1), and Norwegian øre (20/10/5/1). The API in all three languages is the same shape: makeChange(amount, denominations) returns the coin list picked greedily from largest to smallest denomination. The bonus “fixed number of coins per denomination” variant is out of scope for the reference.

This kata ships in Agent Full-Bake mode at high gear (F1 tier): the greedy algorithm is small enough to land as one commit per language, with a brief walkthrough noting there are no builders because the inputs and outputs — an integer amount and an integer coin list — are the domain. Greedy is correct for these canonical coin systems but not for arbitrary denomination sets (e.g. {1, 3, 4} making 6 greedy-picks 4+1+1 instead of the optimal 3+3); the general minimum-coin problem requires dynamic programming. See the repo’s Gears section for when high gear is the right call.