Greatest Common Divisor Editorial

Practice Problem Link: Greatest Common Divisor | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given 2 numbers, find their Greatest Common Divisor (GCD).

Naive Approach

We can loop backward from the smaller of the two numbers, and check if the current number divides both the numbers. As soon as we find such a number, we return it.

Analysis

• Time Complexity: O(min(first_number, second_number))
• Space Complexity: O(1)

Implementation

C++

int gcd(int firstNum, int secondNum) {
   if(firstNum > secondNum) {
       int temp = firstNum;
       firstNum = secondNum;
       secondNum = temp;
   }
   for(int i = firstNum; i >= 1; i--) {
       if(firstNum % i == 0 && secondNum % i == 0) {
           return i;
       }
   }
   return 1;
}

Java

class Solution {
   int gcd(int firstNum, int secondNum) {
       if(firstNum > secondNum) {
           int temp = firstNum;
           firstNum = secondNum;
           secondNum = temp;
       }
       for(int i = firstNum; i >= 1; i--) {
           if(firstNum % i == 0 && secondNum % i == 0) {
               return i;
           }
       }
       return 1;
   }
}

Optimal Approach

To this problem optimally, we will use the Euclidean Algorithm. The algorithm is as follows,

• Base Case: gcd(a, b) = a (if b = 0)
• General Case: gcd(a, b) = gcd(a, a mod b)

The algorithm converges in logarithmic time and returns the gcd of the two numbers.

Analysis

• Time Complexity: O(log(min(first_number, second_number))
• Space Complexity: O(1)

Implementation

C++

int euclideanGCD(int firstNum, int secondNum) {
   if(firstNum == 0) {
       return secondNum;
   }
   return euclideanGCD(secondNum % firstNum, firstNum);
}
int gcd(int firstNum, int secondNum) {
   return euclideanGCD(firstNum, secondNum);
}

Java

class Solution {
   int euclideanGCD(int firstNum, int secondNum) {
       if(firstNum == 0) {
           return secondNum;
       }
       return euclideanGCD(secondNum % firstNum, firstNum);
   }
   int gcd(int firstNum, int secondNum) {
       return euclideanGCD(firstNum, secondNum);
   }
}