GCD of two very large numbers

Concepts Used:

Mathematics

Difficulty Level:

Hard

Problem Statement (Simplified):

For given two large numbers M and N, find their gcd(M,N).

GCD(M,N) is the larget number possible which divides both.

See original problem statement here

Test Case:

Input:
15 130

Output:
5

Explanation:
5 divides 15 and 130 both completely and there exists no number greater than 5 which divides both of them completely.

Solving Approach :

1) For provided numbers, we know N is of size less than or equal to 100, so we would need to store this number in a string.

2) We know we get the remainder less than N always if we divide any number by N.

3) To get the remainder by dividing a number stored String by Number, we calculate the remainder digit by digit. We update the remainder at every digit until all string is iterated.

4) In each iteration, we take the digit and make it greater than our current remainder by multiplying it by 10 and adding it to digit, no we take mod of digit by N and store as our current remainder. After the whole string is iterated, we get our remainder.

5) After we divide M by N and extract it's remainder, now both of them are of in Long Integer range, and we can carry with our Long Division Method for getting gcd(M,N) where M is our new smaller number.

6) Long Division Method: We repeatedly store remainder i.e (Larger number % Smaller number) and update Larger number by Smaller number until smaller number completely divides the larger number. Last Smaller Number after all steps, is our gcd.

Example:

We'll be given with two nmubers out of which one is string and one is long number. Hence we find remainder of string number and long number.

We can dry run above mentioned techinque,let's say given numbers are 143254 and 3, so first we convert 143254 to long number which will be 143254 % 3. We take mod=0, which will store our final value, So,

As we have got our values in integer form, we can now use long division method, to find out gcd of both number that is gcd(n,mod).

Let's take 25 and 135 for example, we find gcd of both using Long Division Method.

As soon as our remainder becomes 0, dividend is our gcd(a,b).

Solutions:

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

long long modBigNumber(char num[], long long m) 
{ 
    long long mod = 0; 

    for (int i = 0; i < strlen(num); i++) { 

        int digit = num[i] - '0'; 

        mod = mod * 10 + digit; 

        mod = mod % m;         
    }

    return mod; 
}

int main()
{
  int test;
  scanf("%d",&test);
  while(test--){

    long long small;
    long long largeF;
    char large[2001];

    scanf("%lld%s",&small,large);
    largeF = modBigNumber(large,small);

    if(largeF==0){
      printf("%lld\n",small);
    }
    else{
      int temp = small;
      small = largeF;
      largeF = temp;

      while(1){
        if(largeF%small==0){
        printf("%lld\n",small);
          break;
        }
        int temp = small;
        small = largeF%small;
        largeF = temp;
      }
    }
  }
}

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

long long modBigNumber(string num, long long m) 
{ 
    long long mod = 0; 

    for (int i = 0; i < num.size(); i++) { 

        int digit = num[i] - '0'; 

        mod = mod * 10 + digit; 

        mod = mod % m;         
    }

    return mod; 
}

int main()
{
  int test;
  cin>>test;

  while(test--){

    long long small;
    long long largeF;
    string large;

    cin>>small>>large;
    largeF = modBigNumber(large,small);

    if(largeF==0){
      cout<<small<<endl;
    }
    else{
      int temp = small;
      small = largeF;
      largeF = temp;

      while(true){
        if(largeF%small==0){
          cout<<small<<endl;
          break;
        }
        int temp = small;
        small = largeF%small;
        largeF = temp;
      }
    }
  }
}

import java.util.*;
import java.io.*;

public class Main {

  static long modBigNumber(String num, long m){
    long mod = 0; 

    for (int i = 0; i < num.length(); i++) { 

        int digit = num.charAt(i) - '0'; 

        mod = mod * 10 + digit; 

        mod = mod % m;         
    }

    return mod; 
  }

  public static void main(String args[]) throws IOException {
      Scanner sc = new Scanner(System.in);
      int test = sc.nextInt();

      while(test!=0){

        long small = sc.nextLong();
        long largeF;
        String large = sc.next();


        largeF = modBigNumber(large,small);

        if(largeF==0){
          System.out.println(small);
        }
        else{
          long temp = small;
          small = largeF;
          largeF = temp;

          while(true){
            if(largeF%small==0){
              System.out.println(small);
              break;
            }
            temp = small;
            small = largeF%small;
            largeF = temp;
          }
        }
        test--;
      }
  }
}

[forminator_quiz id="1157"]

This article tried to discuss Backtracking. Hope this blog helps you understand and solve the problem. To practice more problems on backtracking you can check out MYCODE | Competitive Programming.