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
andnum2
: Store the lengths ofstr1
andstr2
. -
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 slicesstr1
up tolenGDC
characters.
Core Logic
- Find the GCD of the lengths of the two strings using
gdc(num1, num2)
. - Take the first
lenGDC
characters fromstr1
. Let's call this stringx
. - Check if
x
can recreatestr1
andstr2
when repeated certain times (num1 / lenGDC
andnum2 / lenGDC
times). - If yes, return
x
. Otherwise, return an empty string.
Top comments (0)