Here’s problem thirty one:

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

My solution to this wasn’t very pretty — just look at the monstrous for loop below.

result = 2
for b in range(2):
for c in range(5):
if 100*b + 50*c > 200: continue
for d in range(11):
if 100*b + 50*c + 20*d > 200: continue
for e in range(21):
if 100*b + 50*c + 20*d + 10*e > 200: continue
for f in range(41):
if 100*b + 50*c + 20*d + 10*e + 5*f > 200: continue
for g in range(101):
if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g > 200: continue
for h in range(201):
if 100*b + 50*c + 20*d + 10*e + 5*f + 2*g + h == 200:
result += 1
print(result)

Yeah…zero points for style there. I know for a fact that there is a “clever” way of solving this problem, but its explanation was pretty over my head. Essentially this code works by trying (almost) every combination of coins possible and testing it to see if its value is 200. This is slightly streamlined by initially considering two possibilities, 200 and 100 + 100, so that there are less total calculations. This is the reason why *result* is initialized to 2 and there is no loop for the 200 coin. The number of calculations is also reduced by continuing (skipping to the next iteration) the for loop whenever the current value is greater than 200, which also skips all corresponding inner nested loops.

This slight detail allows us to skip most of the 1,922,707,710 calculations needed for a complete brute force solution, and returns an answer in a reasonable amount of time.

*Answer: 73682*

### Like this:

Like Loading...

*Related*

Tags: cycle detection, decimal, length

## Leave a Reply