Coins: Finding a faster approach

general
,
1

I have been trying the Bytelandian gold coins problem but my code runs with “Time limit exceeded” result. I am a little less intimate with recursion. Can anyone help me out.

My code is as follows:

#define MAX(a,b) a>b?a:b

unsigned long int max=0;

int findMax(unsigned long int n)
{
    if(n<12)
    return n;

    else
    {
        max=findMax(n/2)+findMax(n/3)+findMax(n/4);
        return MAX(max,n);
    }

}

int main()
{

    unsigned long int n;

    while(scanf("%lu",&n)!=EOF)
    {
        printf("%lu\n",findMax(n));
    }
    return 0;
}
1 Like
2

How many times does your code compute let say, findMax(2) or findMax(3) ?

The technique is known as memoization. You can store some values on the go to make your code run faster.

2 Likes
3

Ok, I am getting your point but how do I know findMax() of which how many integers should I store…??

Is that a guess I have to make based on problem or is there a specific way to approach it.?

4

It is obvious that you will require findMax(n) for smaller values of n. Now, when you are calculating the findMax(n) you can make slight modification to your code such that if you have already solved a particular value, you don’t need to solve it again.
For eg.
solve(int n)
{
if (alreadysolved[n])
return alreadysolved[n];
/*
Your code…
solve()
*/
}

1 Like
5

Thanks, my code worked and I also got the concept of memoization

6

Nice question.

7

I have been rying the Bytelandian gold coins problem march 2017 printable calendar
onesecondthree

apri 2017 calendar
april calendar 2017
but my code runs with “Time limit exceeded” result. I am a little less intimate with recursion. Can anyone help me out