Problem 031

Project Euler

Coin sums

Problem 31

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?

At first, this problem looks very familiar as one of the Combinatorial problem using generating function to solve, such as this:

R(x) = \frac{1}{1-x} \cdot \frac{1}{1-x^2} \cdot \frac{1}{1-x^5} \cdot \frac{1}{1-x^{10}} \cdot \frac{1}{1-x^{20}} \cdot \frac{1}{1-x^{50}} \cdot \frac{1}{1-x^{100}} \cdot \frac{1}{1-x^{200}}

Unfortunately, this seems more complicated to find x^{200} terms than the original problem itself.

Next,  notice the inherently recursive nature of this problem. The problem can be look at using each coin at a time in the following scenario for £2 coin:

  1. Use the £2 coin.
  2. Use no £2 coin.

Each time a coin is used, a similar with smaller value problem arrives. (e.g. How many different ways can £2 be made using any number of coins \rightarrow using one £2 coin \rightarrow How many different way can 0 be made using any number of coins). The problem will recurse down until it finally found the number of ways for 1p, 2p, 3p, … so on, up to £2. Therefore, instead of recurse down, building up using previous result (dynamic programming) maybe more efficient. Using an outer loop for each coins and inner loop for each the amount starting from the coin value, each way of getting to a certain value is being accumulated:

countWayOf[value] += countWayOf[value - COIN[i]];

where value is the index to an array call countWayOf[] that accumulate all the ways that particular value can represent. COIN{} is an array contain the value of each coin and the index i to access that value.