# Project Euler #31: Coin sums

# Project Euler #31: Coin sums

+ 0 comments My first DP problem. Enjoyed solving it. For people who are stuck with solving this. Please refer the below video and you'll be able to write logic in DP by yourself.

+ 0 comments first solve on projecteular , then forum will provide different ways to tackle problem. Nice problem.

+ 2 comments k = int(input()) for i in range (k): l = int(input()) ways = [0]*100001 ways[0] = 1 for x in [1,2,5,10,20,50,100,200]: for i in range(x, 100001): ways[i] += ways[i-x] print (ways[l]%(10**9+7))

I am getting correct answers for testcases 0 1 and 3, but everything is timeout. How can I optimize this? Thanks.

+ 0 comments Initially, I didn't read "N is given as p and not £". I thought holy sh*t.

I made my program so optimised that it precalc. values upto £10^5 = 10^7p in 232ms on my machine. Later, while submitting I found that it's p. lol

Hint: Use memoization coinvalue-wise. And don't use Modulus opertor for adding. Check for overflow, if it overflow then subtract by modulus value. Modulus operator is costlier than branch followed by subtract.

+ 0 comments at last solved in java. BigInteger helps me a lot. first solve for all 100000 possibilities and then only print answer directly.

Sort 31 Discussions, By:

Please Login in order to post a comment