return a value from the function

#include<stdio.h>
long long a[1000000],i,ans,n;
long long mon(long long n)
{
if(n<1000000)
return a[n];
else
return mon(n/2)+mon(n/3)+mon(n/4);
}
int main()
{
a[0]=0;a[1]=1;a[2]=2;a[3]=3;a[4]=4;a[5]=5;
for(i=6;i<1000000;i++)
{
a[i]=a[i/2]+a[i/3]+a[i/4];
if(a[i]<i)
a[i]=i;ON
}
while(scanf("%lld",&n)!=EOF)
{
ans=mon(n);
printf("%lld\n",ans);
}
return 0;
}

CAN ANYONE EXPLAIN ME THIS CODE FOR THE PROBLEM “COINS” …
AND PLZ EXPLAIN THE RETURN VALUE OF THE FUNCTION MON

Hello @sidashsahil,

This problem, as you might have noticed is clearly recursive, so the function mon is returning a new call to itself with the given denominations.

Then, array a[] is recursively filled inside main function to apply what is known as memoization which allows for repeated recursion states to be stored on a sort of look-up table!!

I hope this helps,

Bruno

1 Like

could you plz tell what is memoization??
and is it correct to call a function inside the same function??
i.e what is final return value in this case?
In short plz expalin the function MON()

@sidashsahil memoization is a technique by which u can avoid solving the same sub-problem again and again as the values are stored…so if u come to a number, say x the second time or maybe many more times…then instead of solving that number by…

mon(x/2)+mon(x/3)+mon(x/4);

you can directly return the value stored in the array…this saves a lot of time…hope this helps…:slight_smile:

see this wikipedia link to know more!!!

and for your second ques:

it is absolutely correct to call a function within it self…this is called recursion…you can think that there are thousands of functions in the code…one calls the second the second calls the third…and so on…when the terminating or base condition is satisfied the last function returns the value to the previous call…and so on and finally the value is returned to the main…so instead of have thousands of different function for the same task…there is just one which calls itself to reach to the base condition…

for the above code…the fxn is 1st called from the main…this time…all the contents of the main are stored on the stack…then the MON fxn is executed…then it calls itself…this time the current instance of the fxn MON is stored on the stack and then the next call is executed…once it reaches the base condition it returns the value to the previous instance of MON fxn…the is the function available on the stack top…and in the end the final result is returned to the main…!!!

3 Likes

could u plz explain its working if I call mon(12)???

and also what is the need to use
scanf("%lld",&n)!=EOF

Hello,

Just to answer your last question about the need of using scanf("%lld",&n)!=EOF and to complete @kunal361’s answer, I can say that on this case, this “trick” was needed because we weren’t said in advance the number of test cases we had on the files our code was tested against.

That is, when you have any given problem, statements on the sentences related to I/O usually start out like:

“First line of input contains an integer, t which stands for the number of test cases to follow (…)”

On problems where we aren’t given this information we must read until the End Of File is found and that’s the reason that syntax is used :slight_smile:

Best regards,

Bruno

1 Like

Tnxs Bruno :)U made my life much easier
One last thing plz tell me y r we returning mon(n/2)+mon(n/3)+mon(n/4) only??
we could have returned n/5+n/6 etc…

good explanation :slight_smile: