GCD of two numbers

Concepts Used:

Mathematics

Difficulty Level:

Easy

Problem Statement (Simplified):

Print gcd of two given numbers.
gcd(m,n) is the largest number possible which divides both.

See original problem statement here

Test Case:

Input:
1
15 140

Output:
5

Explanation:
5 divides 15 and 140 both and no number larger than 5 divides them completely. So 5 is our answer.

Solving Approach :

Bruteforce Approach :

1) We can check all numbers from 1 to the Smaller number, the largest number which divides both numbers is gcd of both numbers.

2) This approach is not efficient as it takes O(Smaller Number) time complexity, we can learn react online and use Long division method for efficient approach.

Efficient Approach :

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 the steps is our gcd..

Example:

Let two numbers are 25 and 135, so its visual representation for above efficient approach will be,

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

So, 5 is our answer.

Solutions:

#include <stdio.h>

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

  while(test--){

    int a, b;
    scanf("%d%d",&a,&b);
    while(1){
      if(b%a==0){
        printf("%d\n",a);
        break;
      }
      int temp = a;
      a = b%a;
      b = temp;
    }

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

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

  while(test--){

    int a, b;
    cin>>a>>b;
    while(true){
      if(b%a==0){
        cout<<a<<endl;
        break;
      }
      int temp = a;
      a = b%a;
      b = temp;
    }

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

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

      while(test!=0){

        int a = sc.nextInt();
        int b = sc.nextInt();
        while(true){
          if(b%a==0){
            System.out.println(a);
            break;
          }
          int temp = a;
          a = b%a;
          b = temp;
        }
        test--;
      }
  }
}
Previous post GCD of two very large numbers
Next post Sort in a unique way

Leave a Reply

Your email address will not be published. Required fields are marked *