Simplify Greatest Common Divisor with Euclidean Algorithm
Tags: webdev, algorithms, typescript, coding
Published: 2023-09-13 15:18:57

# Introduction 

Today I was looking to get the Greatest Common Divisor during a daily LeetCode grind. 

While I used to work with algorithm at work I got rusty and got stuck on a Medium problem where in some step I needed to find the GCD(Greatest Common Divisor). 

So at first let's understand what is a Greatest Common Divisor. 

## GCD 

Let's make it very simple, the GCD is the largest number that can evenly divide two or more numbers. 

It's like finding the biggest number that can go into both numbers without leaving any leftovers.


Example:

For 12 and 18, the GCD is 6 because 6 is the largest number that divides both 12 and 18 evenly. Easy right ?

So the GCD helps us to find a common factor. 

It can also work for strings ! 

## GCG step by step example

Step 1:
  a = 12
  b = 8
  a % b = 4
  (a, b) -> (b, a % b)
  
Step 2:
  a = 8
  b = 4
  a % b = 0
  (a, b) -> (b, a % b)
  
Step 3:
  a = 4
  b = 0 (termination condition)
  
GCD = 4 (the last non-zero remainder)


### GCD of 2 numbers (TypeScript)


```
function findGCD(a: number, b: number): number {
    // Check conidtion that both numbers are positive
    a = Math.abs(a);
    b = Math.abs(b);

     // This part is the algorthim
    // Use the Euclidean algorithm to find the GCD
    while (b !== 0) {
        const temp = b;
        b = a % b;
        a = temp;
    }

    return a;
}

const num1 = 24;
const num2 = 36;

const gcd = findGCD(num1, num2);
console.log(`The GCD of ${num1} and ${num2} is ${gcd}`);

```


### GCD for 2 strings (TypeScript)



```
function gcdOfStrings(str1, str2) {
    // Find the lengths of both strings
    const len1 = str1.length;
    const len2 = str2.length;

    // Calculate the GCD of the lengths using the Euclidean algorithm
    const gcd = (a, b) => (b === 0 ? a : gcd(b, a % b));
    const lengthGCD = gcd(len1, len2);

    // Extract a substring of lengthGCD from str1
    const x = str1.slice(0, lengthGCD);

    // Check if x divides both str1 and str2
    if (x.repeat(len1 / lengthGCD) === str1 && x.repeat(len2 / lengthGCD) === str2) {
        return x;
    } else {
        return "";
    }
}
```

(Also possible to re-use `findGCD()` example from above)

##  Explanation

### The Goal
The code's aim is to find the greatest common divisor (GCD) of two strings. In this case, it's not the numerical GCD but rather a string that can be used to construct both `str1` and `str2` by repeating it.

### Variables and Functions
- `num1` and `num2`: Store the lengths of `str1` and `str2`.
- `gdc(a, b)`: A function to find the GCD of two numbers. This uses the Euclidean algorithm.
- `lenGDC`: Stores the GCD of the lengths of the two strings.
- `x`: The potential GCD string. It slices `str1` up to `lenGDC` characters.

### Core Logic
1. Find the GCD of the lengths of the two strings using `gdc(num1, num2)`.
2. Take the first `lenGDC` characters from `str1`. Let's call this string `x`. 
3. Check if `x` can recreate `str1` and `str2` when repeated certain times (`num1 / lenGDC` and `num2 / lenGDC` times).
4. If yes, return `x`. Otherwise, return an empty string.