How to solve GCD2 in time ?

general
,
1

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
2

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
3

Thanks a lot … Feel really stupid for missing this.

4

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

5

Well, you’ve now.