02 Euclid's Algorithm for GCD

Eculid's Formla for GCD:

$$\text{GCD}(a, b) = \left\{ \begin{array}{ll} b & \text{when } a = 0 \\ a & \text{when } b = 0 \\ GCD(a \% b, b) & \text{when } a > b \\ GCD(a, b \% a) & \text{when } b > a \\ \end{array} \right.$$

Iterative Method

int GCD(int a, int b) {
  while((a % b) > 0) {
    int temp = a;
    a = b;
    b = temp % b;
  }
  return b;
}

Recursive Method

int gcd(int a, int b) 
{  
    
    // BASE CASE
    if (a == 0) 
       return b; 
    if (b == 0) 
       return a;   
    if (a == b) 
        return a; 
  
    // a is greater 
    if (a > b) 
        return gcd(a % b, b); 
    return gcd(a, b % a); 
}

Question 1

Loading...LeetCode

LeetCode: Find Greatest Common DIvisor of Array

Solution

Iterative Solution

#define ALL(v) v.begin(), v.end()
class Solution {
public:
    
    int findGCD(vector<int>& nums) {
        int a = *max_element(ALL(nums));
        int b = *min_element(ALL(nums));
        
        while((a % b) > 0) {
            int temp = a;
            a = b;
            b = temp % b;
        }
        
        return b;
    }
};

Recursive Solution

#define ALL(v) v.begin(), v.end()
class Solution {
public:
    inline int gdc(const int &a, const int &b) {
        if(a == 0)
            return b;
        if(b == 0)
            return a;
        if(a == b)
            return a;
        
        if(a > b)
            return gdc(a % b, b);
        return gdc(a, b % a);
    }
    
    int findGCD(vector<int>& nums) {
        return gcd(*min_element(ALL(nums)), *max_element(ALL(nums)));
    }
};

Question 2

Loading...LeetCode

LeetCode: Greatest Common Divisor of Strings

Solution

class Solution {
public:
    inline int gcd(const int &a, const int &b) {
        if(a == 0)
            return b;
        if(b == 0)
            return a;
        if(a == b)
            return a;
        
        if(a > b)
            return gcd(a % b, b);
        return gcd(a, b % a);
    }
    
    string gcdOfStrings(string str1, string str2) {
        return ((str1 + str2 == str2 + str1) 
                ? (str1.size() < str2.size() 
                   ? str1 
                   : str2).substr(0, gcd(str1.size(), str2.size())) 
                : "");
    }
};