Greatest common divisor

This time we are going to talk about a tiny clever algorithm for finding the GCD between 2 numbers. The algorithm is known as the Euclidean algorithm and was invented by Euclid in the 300BC, one of the oldest algorithms in common use.

What is GCD?

The GCD between two numbers is just the largest divisor between both.

Naive GCD calculation

Simplest way to calculate the divisors of a number is just brute-force. We iterate over all numbers in the range [1...n] and store all values where the remainder between dividing n and the number is 0.

Set<Integer> gcd(int number) {
    Set<Integer> divisors = new HashSet<>();

    for (int i = 1; i <= number; i++) {
        if (n % i == 0) divisors.add(i);
    }

    return divisors;
}

Then, we can do the same for both numbers and find the maximum divisor common to both numbers.

int gcd(int largest, int smallest) {
    Set<Integer> gcd1 = gcd(largest);
    Set<Integer> gcd2 = gcd(smallest);

    // Largest value in intersection
    return gcd1.retainAll(gcd2).stream().max(Comparator.naturalOrder()).orElseThrow();
}

But this is just inneficient and boring. Let’s see what Euclid proposes.

Euclidean algorithm

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number. Since this replacement reduces the larger of the two numbers, repeating this process gives successively smaller pairs of numbers until the two numbers become equal. When that occurs, they are the GCD of the original two numbers.

What does that mean? That the algorithm is a recursive algorithm that starts dealing with smaller numbers in each call, and by doing that at some point it will magically (magically as in complex math, something like mathgically) arrive to the solution (the largest divisor) or the minimum common divisors of all natural numbers 1. So it’s a top-down approach.

It all starts with expressing the largest number as a factor of the smallest. Let’s use for our example 1071 and 462.

2 important pieces of information:

• 1071 / 462 = 2
• 1071 % 462 = 147

So 1071 can be expressed as 1071 = 462 * 2 + 147. This is just decomposing the division into a multiplication and a sum.

In a more general form large number = small number * divisor + remainder.

Then, the algorithm leverages the following mathematical property:

gcd(a, b) = gcd(b, r)

Where a = b * q + r. So if we can solve gcd(smallest, remainder) then we will find the answer to the question gcd(largest, smallest).

Let’s take this a step further as we haven’t finished yet. We are now going to decompose 462 by using the remainder.

462 = 147 * 3 + 21

In code this would be something like:

remainder = largest % smallest;
largest = smallest;
smallest = remainder;

Let’s do another round:

147 = 21 * 7 + 0

And because the remainder is now 0, that means that we have found our answer 21.

Maybe the same example in pen and paper helps to bring some clarity to the logic:

Code

Our final version of the recursive algorithm with some extra sanitization.

int gcd(int largest, int smallest) {
    // Input sanitization
    if (smallest > largest) return gcd(smallest, largest);
    
    int remainder = largest % smallest
    
    // Smallest is the first (thus the largest) divisor found
    if (remainder == 0) return smallest;    
    
    return gcd(smallest, remainder);
}

GCD of a String

The reason why I ended up reading about GCD is because I was working on a coding challenge and wondered…

Is there a better way of doing this?

– Pablo

I found that asking myself that question regardless of me solving the challenge or not, always leads me to checking other people solutions and that’s where I learn the most.

Enough chit chat, let’s jump into the problem I was working on.

Let’s think about it for a moment

A priori the problem looks nothing like calculating GCD between two numbers, but actually they are more similar than what you might think at first.

• We have 2 inputs, a largest and a smallest.
• Largest input can be expressed as largest = smallest * divisor + remainder.

But how do we even do a division between Strings?

We can use startsWith method to check if a String is divisible by another.

Example:

Largest	Smallest	Divisible
ABABAB	ABAB	true
ABABAB	AB	true
ABABAB	A	true
ABABAB	AC	false

But this is not enough to solve our problem, because we need to find a divisor that gives us a remainder of zero in order to find our GCD.

How do we find the remainder? We can just take the portion of the largest input that comes after the divisor. Let’s expand our previous example.

Largest	Smallest	Divisible	Remainder
ABABAB	ABAB	true	AB
ABABAB	AB	true	ABAB
ABABAB	A	true	BABAB
ABABAB	AC	false	-

And from now on we can just simply apply the Euclidean algorithm and recurse with the smallest taking the place of the largest and the remainder taking the place of the smallest.

Let’s do a full example and notice how largest = smallest + reminder

// 1 iteration
largest = "ABABAB"
smallest = "ABAB"
remainder = "AB"

// 2 iteration
largest = "ABAB"
smallest = "AB"
remainder = "AB"

// 3 iteration
largest = "AB"
smallest = "AB"
remainder = "" 

Code

public String gcdOfStrings(String largest, String smallest) {
    // Input sanitization
    if (smallest.length() > largest.length()) return gcdOfStrings(smallest, largest);
    
    if (largest.startsWith(smallest)) {
        String remainder = largest.substring(smallest.length());

        if (remainder.isEmpty()) return smallest;
        
        return gcdOfStrings(smallest, remainder);
    }
    
    return "";
}

Tough problem. I don’t expect anybody to come up with this clever solution, and even myself I’m not sure I understand how the magical Euclidean algoritm solves the GCD problem. Anyway, I still thought it was interesting to talk about it as I struggled a bit while searching for explanations to this leetcode challange.