alexcuesta

My tech blog

Just another coin change problem

leave a comment »

Few weeks ago I was given a paper with problems in the latest Silicon Milkround here in London. One of the problems was the classic coin change problem that most of us had to solve in the University. To my surprise, I felt very rusty to solve it now! Basically because in my professional environment I usually spend more time debugging and refactoring code than solving problems like this.

As I love this kind of problems and wanted to challenge myself, I wrote my specific problem and solution and I want to share it with you. Basically, there are three different coin change problems:

  • return the minimum number of coins needed for a give change
  • return the number of different coin combinations for a given change
  • return all coin combinations for a given change

The problem I solved was the last one about returning all combinations which is generic and can be used to answer the two other problems.

Next you can find the problem illustrated as a set tests:

package coins.change.combinations;

import static org.junit.Assert.*;

import java.util.List;

import org.junit.Test;

public class CoinsChangeCombinationsTest {

	@Test
	public void changeOf1() {
		int change = 1;
		Coin[] coins = {Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(1, coinsChange.size());
		assertEquals("c", coinsChange.get(0));
	}

	@Test
	public void changeOf4() {
		int change = 4;
		Coin[] coins = {Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(1, coinsChange.size());
		assertEquals("cccc", coinsChange.get(0));
	}

	@Test
	public void changeOf5WithCents() {
		int change = 5;
		Coin[] coins = {Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(1, coinsChange.size());
		assertEquals("ccccc", coinsChange.get(0));
	}

	@Test
	public void changeOf5WithNickelAndCents() {
		int change = 5;
		Coin[] coins = {Coin.NICKEL, Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(2, coinsChange.size());
		assertEquals("n", coinsChange.get(0));
		assertEquals("ccccc", coinsChange.get(1));
	}

	@Test
	public void changeOf6WithNickelAndCents() {
		int change = 6;
		Coin[] coins = {Coin.NICKEL, Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(2, coinsChange.size());
		assertEquals("nc", coinsChange.get(0));
		assertEquals("cccccc", coinsChange.get(1));
	}

	@Test
	public void changeOf6WithCents() {
		int change = 6;
		Coin[] coins = {Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(1, coinsChange.size());
		assertEquals("cccccc", coinsChange.get(0));
	}

	@Test
	public void changeOf10WithCents() {
		int change = 10;
		Coin[] coins = {Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(1, coinsChange.size());
		assertEquals("cccccccccc", coinsChange.get(0));
	}

	@Test
	public void changeOf10WithNickelAndCent() {
		int change = 10;
		Coin[] coins = {Coin.NICKEL, Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(3, coinsChange.size());
		assertEquals("nn", coinsChange.get(0));
		assertEquals("nccccc", coinsChange.get(1));
		assertEquals("cccccccccc", coinsChange.get(2));
	}

	@Test
	public void changeOf11WithNickelAndCent() {
		int change = 11;
		Coin[] coins = {Coin.NICKEL, Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(3, coinsChange.size());
		assertEquals("nnc", coinsChange.get(0));
		assertEquals("ncccccc", coinsChange.get(1));
		assertEquals("ccccccccccc", coinsChange.get(2));
	}
	@Test
	public void changeOf15WithDimeNickelAndCent() {
		int change = 15;
		Coin[] coins = {Coin.DIME, Coin.NICKEL, Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(6, coinsChange.size());
		assertEquals("dn", coinsChange.get(0));
		assertEquals("dccccc", coinsChange.get(1));
		assertEquals("nnn", coinsChange.get(2));
		assertEquals("nnccccc", coinsChange.get(3));
		assertEquals("ncccccccccc", coinsChange.get(4));
		assertEquals("ccccccccccccccc", coinsChange.get(5));
	}

	@Test
	public void changeOf20WithDimeNickelAndCent() {
		int change = 20;
		Coin[] coins = {Coin.DIME, Coin.NICKEL, Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(9, coinsChange.size());
		assertEquals("dd", coinsChange.get(0));
		assertEquals("dnn", coinsChange.get(1));
		assertEquals("dnccccc", coinsChange.get(2));
		assertEquals("dcccccccccc", coinsChange.get(3));
		assertEquals("nnnn", coinsChange.get(4));
		assertEquals("nnnccccc", coinsChange.get(5));
		assertEquals("nncccccccccc", coinsChange.get(6));
		assertEquals("nccccccccccccccc", coinsChange.get(7));
		assertEquals("cccccccccccccccccccc", coinsChange.get(8));
	}
	@Test
	public void changeOf20WithQuarterDimeNickelAndCent() {
		int change = 20;
		Coin[] coins = {Coin.QUARTER, Coin.DIME, Coin.NICKEL, Coin.CENT};

		List coinsChange = CoinsChangeCombinations.changeOf(change, coins);

		assertEquals(10, coinsChange.size());
		assertEquals("q", coinsChange.get(0));
		assertEquals("dd", coinsChange.get(1));
		assertEquals("dnn", coinsChange.get(2));
		assertEquals("dnccccc", coinsChange.get(3));
		assertEquals("dcccccccccc", coinsChange.get(4));
		assertEquals("nnnn", coinsChange.get(5));
		assertEquals("nnnccccc", coinsChange.get(6));
		assertEquals("nncccccccccc", coinsChange.get(7));
		assertEquals("nccccccccccccccc", coinsChange.get(8));
		assertEquals("cccccccccccccccccccc", coinsChange.get(9));
	}
}

And my recursive “divide and conquer” implementation is here:

package coins.change.combinations;

import java.util.ArrayList;
import java.util.List;

public class CoinsChangeCombinations {

	public static List changeOf(int total, Coin[] coins) {
		return findCombinations("", total, coins, 0);
	}

	private static List findCombinations(String prefix, int total, Coin[] coins, int coinIndex) {
		List combinations = new ArrayList();
		Coin currentCoin = coins[coinIndex];

		if (coinIndex==coins.length-1) {
			combinations.add(prefix + addCoins(total, currentCoin.symbol));
		} else {
			int bigCoins = total / currentCoin.value;

			for (int i=bigCoins; i>=0; i--) {
				int partial = i * currentCoin.value;
				int remaining = total - partial;
				combinations.addAll(findCombinations(prefix + addCoins(i, currentCoin.symbol), remaining, coins, coinIndex+1));
			}
		}

		return combinations;
	}

	public static String addCoins(int change, char coinSymbol) {
		StringBuilder sb = new StringBuilder();
		for (int i=0; i<change; i++) {
			sb.append(coinSymbol);
		}
		return sb.toString();
	}

}

And the Coin class:

package coins.change.combinations;

public enum Coin {
	CENT(1, 'c'), NICKEL(5, 'n'), DIME(10,'d'), QUARTER(20, 'q');

	public final int value;
	public final char symbol;

	private Coin(int value, char symbol) {
		this.value = value;
		this.symbol = symbol;
	}
}

Written by alexcuesta

June 22, 2013 at 11:05 pm

Posted in Java

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: