Implementing basic Mathematical operations (Euclidean algorithm for GCD)

Problem Statement – Given two non-negative integers a and b, you’ve to find the Greatest Common Divisor (GCD) or Highest Common Factor (HCF) of the two numbers. In other words, find the largest number that divides them both.

Euclidean Algorithm

The Euclidean algorithm is one of the oldest numerical algorithms to compute the greatest common divisor (gcd) of two positive integers.

Euclidean Using subtraction

GCD (a, b)
1. if a==0:
2.   return b
3. while b != 0:
4.   if (a>b)
5.     a = a-b
6.   else
7.     b = b-a
8. return a

Time Complexity: O(n) where n = a+b

Euclidean Using division

GCD (a, b)
1. if b == 0:
2.   return a
3. else  
4.   return GCD (b, a mod b);

Time Complexity: O(log(n)) where n = a+b

Code Implementation

//
//  main.cpp
//  GCD
//
//  Created by Himanshu on 19/09/21.
//

#include <iostream>
using namespace std;

int gcdUsingSubtarction (int a, int b) {
    if (a == 0) {
        return b;
    }

    while (b != 0) {
       if (a>b)
          a = a - b;
      else
         b = b - a;
     }
    return a;
}

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

int main() {
    int a = 7, b = 43;
    
    printf("GCD of %d and %d using subtraction is %d \n", a, b, gcdUsingSubtarction(a, b));
    printf("GCD of %d and %d using division is %d \n", a, b, gcdUsingDivision(a, b));
    
    a = 21;
    b = 343;
    
    
    printf("GCD of %d and %d using subtraction is %d \n", a, b, gcdUsingSubtarction(a, b));
    printf("GCD of %d and %d using division is %d \n", a, b, gcdUsingDivision(a, b));
    
    return 0;
}

Output

GCD of 7 and 43 using subtraction is 1 
GCD of 7 and 43 using division is 1 
GCD of 21 and 343 using subtraction is 7 
GCD of 21 and 343 using division is 7 

Here’s a working example:

https://ideone.com/lZM5kX

Practice problem

https://www.codechef.com/problems/SHUTTLE

Solution (You should try to solve this problem yourself first)

https://www.codechef.com/viewsolution/3241139