In the United Kingdom the currency is made up of pound (£) and pence (p). 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?
This is a classic math problem. A simple approach is to consider 200 pound coin first. We can either choose to use it or not. Then, see the leftovers and see how many 100 pound coin we can use, then see the leftover count, and see how many ways we can utilize 50 pence coin, and so on. If at anytime the 200 value is achieve, we exit the for loops and increment our solution by 1. Code wise, looks dirty. Nested for loops don't look so good...
Answer: 73682
Runtime: 15 ms