Program to find the GCD of two numbers in javascript.

An algorithm to find the GCD of two numbers in javascript.

We will implement a simple algorithm with different approaches to find the gcd of two numbers in javascript. Everything will be written in ES6.

Example

Input:
60 15
36 60

Output:
15
12

Iterative approach.

Implementation

• We will loop until both the given numbers are not eqaul.
• Then in each iteration we will check if num1 is greater than num2 or not.
• If it is greater then we will subtract num2 from num1 else we will subtract num1 from num2.
• This approach is based on Euclidean Algorithm.

let gcd = (num1, num2) => {
  
  //Loop till both numbers are not equal
  while(num1 != num2){
    
    //check if num1 > num2
    if(num1 > num2){
      //Subtract num2 from num1
      num1 = num1 - num2;
    }else{
      //Subtract num1 from num2
      num2 = num2 - num1;
    }
  }
  
  return num2;
}

Input:
console.log(gcd(60, 15));
console.log(gcd(60, 36));

Output:
15
12

Time complexity: O(log(a) + log(b)) = O(n).
Space complexity: O(1).

Time and Space complexity

• In each iteration we are reducing any one number by the other number, so Time complexity is O(log(a) + log(b)).
• We are using constant space, so Space complexity is O(1).

Recursive Approach

• We are going to implement the above approach with recursion.
• We are going to check if num2 is 0 then return num1.
• Else call the same function recursively with num2 and remainder of num1 % num2.

let gcd = (num1, num2) => {
   //if num2 is 0 return num1;
   if(num2 === 0){
      return num1;
   }
   
   //call the same function recursively
   return gcd(num2, num1 % num2);

}

Input:
console.log(gcd(60, 15));
console.log(gcd(36, 60));

Output:
15
12

Time complexity: O(n) or O(log(a) + log(b)).
Space complexity: O(m + n).

Time and Space complexity

• We are calling the same function recursively till the num2 is 0 and each call num1 and num2a are getting reduced, so Time complexity is O(n) or O(log(x) + log(y)).
• Each recursive function is stored in call stack and it is called until num2 is not 0, so Space complexity is O(n + m).