# Project Euler #31: Coin sums

# Project Euler #31: Coin sums

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

+ 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.

+ 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 30 Discussions, By:

Please Login in order to post a comment