Problem Code : COINS (Wrong Answer) Help

Problem

Updated Solution

Getting wrong answer for the above solution.

Your solution fails for multiple inputs means it output the answer only for first input where as required answer should be for all of the inputs.

ex :
INPUT:
8
10
Expected result:
8
10
Result found :
8

I think now you have got your mistake.

Updated Solution
Still wrong answer.

I am sorry I don’t know python that much . I have no idea what function you are using ‘re’. Though I can tell you the inputs where it is failing.
ex n=100, expected ans=120.

It requires DP.

I’m sorry I don’t understand how the answer is 120 for n = 100 and not 108. I’m not using DP, Just using a cheap trick of regular expressions (re).

1 Like

https://www.algorithmist.com/index.php/SPOJ_COINS

Use this recursion relation

F(0)=0
F(1)=1
F(n)=max(F(n/2)+F(n/3)+F(n/4),n) for all n greater than 2

I think this will help