Understanding Recursion flow in Bytelandian problem

general
1

Hi all,
This may be a naive questions.But I am unable to figure it out how recursive flow is being happening in the solution to this problem.Recursion is my weak point and I am unable to understand how things jump from one piece of code to another in recursion. I understand the basic level recursion where you break when certain condition meets.but herein i am not able to understand.
Is there anybody who is proficient in recursion ,please help!

Question: COINS Problem - CodeChef

Solution: (Skip the unnecessary printf statements in between the funct.)
#include <stdio.h>

long long funct(long long);
 
long long memory[10000000]={0};
 
int main() {
long long n=0, m=0;
 
    while(scanf("%lld", &n)!=EOF) {
    printf("%lld\n", funct(n));
    }
    return 0;
}
 
long long funct(long long n) {
 
 
    if(n<12)
    return n;
    
    if(n==12)
    return 13;
    
    if(n<1000000) {
        if(memory[n]!=0){
        return memory[n];printf("here inside it");}
    }
printf("n is :%d\n",n);
    long long two, three, four;
    two=n/2;
    three=n/3;
    four=n/4;
    long long k =funct(two)+funct(three)+funct(four);
   printf("k is %d\n",k);
   // printf("funct(two) is: %lld\n",funct(two));
    if(n<1000000){printf("inside if\n");
    memory[n]=k;}
    printf("one end\n");
    //printf("k here %lld\n :",k)
    return k;
}
1 Like
2

In this problem, clearly the boundary condition is when you have a coin with number less than 12.

As you can obseve, for any coin less than 12, there is no configuration, such that you can get it exchanged with dollars more than the coin’s value!

Now we need to consider what happens when n is greater than 12! The bank replaces the coin with one n/2, one n/3 and one n/4 coin. To maximise the amount we need to replace them further till each coin after replacement is greater than or equal to 12(as it will reduce the total amount if we exchange them further!).

3 Likes