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.