Problem 31(Coin sums)

Problem 31(Coin sums)

In England the currency is made up of pound, £, and pence, p, and there are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

 

In Python:

#PE31 Coin sums
import time

startTime = time.time()

def func(change, coins, k):
    if change - k * coins[0] == 0:
        return 1
    elif change - k * coins[0] > 0 and len(coins) == 2:
        return 1
    elif change - k * coins[0] < 0:
        return 0
    else:
        return sum(func(change - k * coins[0], coins[1:], l) for l in range(0, (change - k * coins[0]) // coins[1] + 1))

coins = [200, 100, 50, 20, 10, 5, 2, 1]
print(func(200, coins, 0) + func(200, coins, 1))
print(time.time() - startTime, "seconds")

Run time: 0.12133002281188965 seconds

 

 

In Java:

package project_euler31_40;

public class Euler31 {
	public static int func(int change, int coinNum, int k) {
		int[] coins = {200, 100, 50, 20, 10, 5, 2, 1};
		if (change - k * coins[coinNum] == 0) {
			return 1;
		}
		else if (change - k * coins[coinNum] > 0 && coinNum == 6) {
			return 1;
		}
		else if (change - k * coins[coinNum] < 0) {
			return 0;
		}
		else {
			int sum = 0;
			int n = Math.floorDiv(change - k * coins[coinNum], coins[coinNum + 1]) + 1;
			for (int i = 0; i < n; i++) {
				sum += func(change - k * coins[coinNum], coinNum + 1, i);
			}
			return sum;
		}
	}
	public static void main(String[] args) {
		long startTime = System.currentTimeMillis();
		System.out.println(func(200, 0, 0) + func(200, 0, 1));
		long endTime = System.currentTimeMillis();
		System.out.println((double)(endTime - startTime)/(double)1000 + "seconds");
	}
}

Run time: 0.008seconds

 

Solution: 73682