1 reply to this topic

[nitin28]

Sphere Online Judge (SPOJ) - Problem COINS

i have used recursive function to solve problem given in above link.

12
2
50
10000
10000000
100000000
1000000000

i have run above test cases. All the test cases are running fine except the last 2, showing time limit exceeded and signal(SIGXCPU). If I change the datatype to long int then second last test case is showing output. i can't find the logic behind this.

i can't understand why it is showing error for a particular case when it falls within the range of long long int.

i am using gcc-4.3.4 compiler and running on Ideone.com

#include<stdio.h>


long long int calc(long long int n)

{

     long long int x,y,z,sum;

     x=y=z=sum=0;

     

     if(n>1)

     {

     x=calc(n/2);

     y=calc(n/3);

     z=calc(n/4);

     sum =x+y+z;

     if(sum<n) 

     {

               sum=n;          

     }    

     

     return sum;

     }

     

     else

     {

         return n;    

     }

     

} 



int main()

{

long long int sum,n;


while(scanf("%lld",&n)!=EOF)

{

         

                

                

                sum=calc(n);

                

                printf("\n%lld",sum);

}


return 0;    

}

[kernelcoder]

First, perhaps the problem is in your logic. It is taking too much time to finish (that's why you are getting "signal(SIGXCPU)").
Second: Have you considered the recursion stack size?