# How to solve GCD2 in time ?

I am getting a TLE for my submission for GCD2 … As far as I can tell, I am doing exactly what a lot of accepted solutions are doing. Please help me.

``````#include <stdio.h>
#include <string.h>

#define MAX_LENGTH 260 + 1

int gcd(int a, int b) //b is always smaller than a
{
if(b == 0)
return a;
else
return gcd(b, a%b);
}

int get_remainder(char b[], int a)
{
int i, r = 0, no_of_digits = strlen(b);

//Evaluate big num like a polynomial mod small num
for(i = 0; i <  no_of_digits; i--)
{
r = r*10 + (b[i] - '0');
r %= a;
}

return r;
}
``````

int main()
{
char b[MAX_LENGTH];
int t, a;
scanf("%d", &t);

``````   while(t--)
{
scanf("%d %s",&a, b);

if(a == 0)
printf("%s\n",b);
else
printf("%d\n", gcd(a, get_remainder(b, a)) );

}

return 0;
}``````
1 Like

In the for loop in the function get_remainder(char b[], int a), “i–” should be “i++”.

This should be changed

``````for(i = 0; i <  no_of_digits; i--)
``````

To this

``for(i = 0; i <  no_of_digits; i++)``
1 Like

Thanks a lot … Feel really stupid for missing this.

I don’t have the points to upvote your answer … Or I would.

Well, you’ve now.

//