SPOJ: GCD2

Problem Link

http://www.spoj.com/problems/GCD2/

Problem Description

In this problem, we need to find greatest common divisor(GCD) of two numbers.
If there are two numbers, say A and B, then the constraints are :
1. 0<=A<=40000(can be stored in integer)
2. A<=B<=10^250 (can not be stored in integer)

Concepts Used

Recursion and Maths

Code

#include <bits/stdc++.h>
using namespace std;

//function to find the GCD of two numbers using Eucliedean's algorithm
int gcd(int a, int b) {

    if(b==0) {
        return a;
    }
    else {
        return gcd(b,a%b);
    }
}

int main()
{
    int t, i;
    int a, b;
    char num[300];

    scanf("%d",&t);                          

    while(t--)  {
        scanf("%d%s",&a,num);                //two inputs, a number and a character array

        if(a==0)                             //if number first number is 0, then ans would be the second number
        {
            printf("%s\n",num);
            continue;
        }

        int len = strlen(num);         //computing the length of the character array
        b = 0;                                    //initializing b to 0

        for(i=0;i<len;i++) {              //reading the array character by character
            b = (b*10+(num[i]-'0'))%a;  //maintaining the remainder i.e b%a (Why?See the explaination below)
        }

        printf("%d\n",gcd(a,b));             //finding the gcd of the first number and the number formed from the above loop  
    }

    return 0;
}

Explanation

The problem can be solved using the Euclid's algorithm for finding GCD of two numbers.

A can be stored in an integer variable but B can't be stored in integer, so it has to be stored in character array or string.
We already know that,
gcd(b,a) = gcd(a,b%a)

Now, what we basically want to do is bring down the range of B to the integer range.

Here, we perform steps similar to basic arithmetic division for calculating a%b.

For example, in order to find 467%3.
1. We take the first digit 4, and do 4%3, which is equal to 1.
2. Then, I bring down the number 1. So, the new number becomes 16. 16%3 will be 1.
3. Bring down 1. the new number will be 17. Again, 17%3 will be 2.
Hence 467%3 = 2.

So, the logic is to read the number digit by digit and maintain the remainder.

This content has been helpful to you?

Thanks for contributing!

Yes No