Project Euler Problem 31 Statement

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?

Solution

Project Euler Problem 31 asks us to determine how many ways we can make £2 (200 pence) using any combination of British coins. The coins available are 1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p). The solution provided is an efficient way to solve this combinatorial problem using dynamic programming. Here's an in-depth breakdown of how it works:

Problem Restatement

The task is to count the number of distinct ways to form a target value (200 pence) using given coin denominations. Each coin can be used any number of times, including zero.

Solution Analysis

The Python solution leverages a concept called dynamic programming (DP), specifically a DP array that records the number of ways to form each possible sum up to the target. Here's how each part of the solution works:

Step 1: Define Target and Coins

target = 200
coins = [1, 2, 5, 10, 20, 50, 100, 200]

• target = 200 sets the goal: we want to find all combinations that sum up to 200 pence.
• coins = [1, 2, 5, 10, 20, 50, 100, 200] is a list of coin denominations in pence.

Step 2: Initialize Ways Array

ways = [1] + [0]*target

• ways is a list where ways[i] represents the number of ways to achieve a sum of i pence using the available coins.
• [1] + [0]*target initializes ways with target + 1 elements: the first element is set to 1, and all others are set to 0.

  Setting ways[0] = 1 is a base case that represents the fact that there is exactly one way to make a total of 0 pence (by using no coins at all).

Step 3: Dynamic Programming Iteration Over Each Coin

for coin in coins:
    for i in range(coin, target + 1):
        ways[i] += ways[i - coin]

This section uses nested loops to build up the number of ways to form each value from 1 to target. Let's break down each part:

1. Outer Loop (for coin in coins):
   • The outer loop iterates over each coin denomination in the coins list. For each coin, we update the ways array to reflect how many additional ways to achieve each sum are possible with this coin.
2. Inner Loop (for i in range(coin, target + 1)):
   • For each coin, the inner loop iterates from coin to target. This range is chosen because we only need to consider sums that are at least as large as the coin's value (e.g., there's no way to form 5 pence with a 10p coin alone). target+1 is used to include target for consideration
3. Dynamic Programming Update (ways[i] += ways[i - coin]):
   • For each i, ways[i] is updated by adding ways[i - coin].
     Explanation: ways[i - coin] represents the number of ways to make the value i - coin using the available coins. By adding coin to any way of making i - coin, we obtain a way of making i. Therefore, ways[i] accumulates the count of ways to make i by considering the addition of the current coin denomination.
   • This update step ensures that each ways[i] contains the total number of distinct ways to achieve the sum target after considering all coins up to the current one.

Step 4: Output the Result

print("Ways to make change =", ways[target])

Example Walkthrough

Let's go through a smaller example with a target of 5 and coins [1, 2, 5] to clarify how the solution works.

1. Initialization:

   target = 5
   coins = [1, 2, 5]
   ways = [1, 0, 0, 0, 0, 0]

2. Processing Coin 1: For each i from 1 to 5, add ways[i - 1] to ways[i]:

   i = 1: ways[1] += ways[0] → ways = [1, 1, 0, 0, 0, 0]
   i = 2: ways[2] += ways[1] → ways = [1, 1, 1, 0, 0, 0]
   i = 3: ways[3] += ways[2] → ways = [1, 1, 1, 1, 0, 0]
   i = 4: ways[4] += ways[3] → ways = [1, 1, 1, 1, 1, 0]
   i = 5: ways[5] += ways[4] → ways = [1, 1, 1, 1, 1, 1]

3. Processing Coin 2: For each i from 2 to 5, add ways[i - 2] to ways[i]:

   i = 2: ways[2] += ways[0] → ways = [1, 1, 2, 1, 1, 1]
   i = 3: ways[3] += ways[1] → ways = [1, 1, 2, 2, 1, 1]
   i = 4: ways[4] += ways[2] → ways = [1, 1, 2, 2, 3, 1]
   i = 5: ways[5] += ways[3] → ways = [1, 1, 2, 2, 3, 3]

4. Processing Coin 5: For each i from 5 to 5, add ways[i - 5] to ways[i]:

   i = 5: ways[5] += ways[0] → ways = [1, 1, 2, 2, 3, 4]
   The final value of ways[5] is 4, which means there are four ways to make 5 pence with coins [1, 2, 5]

Complexity and Efficiency

This solution has a time complexity of O(n×m), where n is the target amount and m is the number of coin denominations. This is efficient for problems of this type because each value up to target is computed only once for each coin.

Conclusion

The dynamic programming approach in this solution avoids the need for more complex recursive combinations, making it highly efficient. The ways array efficiently builds up the count of combinations by leveraging previously computed results, providing an elegant solution to the coin-sum problem.

HackerRank version

Solves all test cases for Hackerrank Project Euler Problem 31

HackerRank Project Euler 31 changes the target total from £200 to a variable target £1 ≤ N ≤ £10⁵

Last Word

• Further reading: Dynamic Programming Solution to the Coin Changing Problem

• From Dr. Lee A. Newberg:
  For 2x pounds the number of ways to make change with coins of 1, 2, 5, 10, 20, 50, 100, and 200 pence is:
  Ways(2x) = (63 - 16524x + 121100x^2 + 862127x^3 + 1656620x^4 +1395380x^5 + 543200x^6 + 80000x^7) / 63.
  I can compute that pretty quickly even for 10^12 pounds!