GCD For Competitive Programming

Hello guys, welcome back to “code with asharam”. I know you would have got tired of hearing long break excuses every time I write a new post. So, this time I won’t make any excuse for 17 day long break. As you might have noticed until now that I will write about GCD in this post. Not only this post but also in next few posts, I will covering most of basic and advanced mathematics you will encounter in your competitive programming journey. So, without any further delay, let’s take a dive into deep oceans of mathematics.

GCD

This is one of the most basic mathematics topic you will encounter in competitive programming. Most of you would have learned about Greatest Common Divisor in middle school itself. GCD of two numbers $a$ and $b$ is defined as largest number $c$ which divides both $a$ and $b$. For example $GCD(4, 6) = 2$ and $GCD(8, 9) = 1$. I will use the notation $x|y$ to denote that $y$ is divisible by $x$. There are some important properties GCD:

  1. Since $GCD(a, b) = c$ divides both $a$ and $b$, we can write $a = ck_1$ and $b = ck_2$ where $k_1, k_2$ are integers.\[
    \begin{array}{c}
    a + b = ck_1 + ck_2 = c(k_1 + k_2) \implies c | (a+b) \\
    a – b = ck_1 – ck_2 = c(k_1 – k_2) \implies c | (a-b) \\
    a * b = ck_1 * ck_2 = c^2k_1*k_2 \implies c | (a*b) \\
    a / b = ck_1 / ck_2 = k_1/k_2 \nRightarrow c | (a/b)
    \end{array}
    \]
  2. As you can see that $GCD(a, b)$ divides $a+b, a-b, a*b$ but it may or may not divide $a/b$. Hence, we can say that $GCD(a, b) = GCD(a, a+b) = GCD(a, a-b)$ and $GCD(a, a*b) = a$.
  3. I think all of you are familiar with modulo operator $\%$. $a%b$ returns the remainder left when $a$ is divided by $b$. Mathematically, $$a\%b = a – [a/b]*b $$ Clearly, what we are doing is subtract $b$ from $a [a/b]$ times. Also, $$GCD(a, b) = GCD(a-b, b) = GCD(a-2b, b) = GCD(a-kb, b)$$ Hence, we can say that $GCD(a, b) = GCD(a\%b, b)$.

I have covered almost every important point about GCD. Let’s now see about the common algorithms used to find GCD.

Simple Brute Force

As you know that $GCD(a, b)$ is divides both $a$ and $b$ which implies $GCD(a, b) \leq min(a, b)$. Hence, we can simple run a loop from $0$ to $min(a, b)$ and find the largest integer which divides both $a$ and $b$. This algorithms take $O(min(a, b))$ time and $O(1)$ space and is not much efficient for large numbers.

Based on $GCD(a, b) = GCD(a-b, b)$

This algorithm uses the results in 1st point. Since, $GCD(a, b)$ does not changes even after replacing larger number with difference of two numbers, we can simply keep on repeating this until one of the number becomes $0$ and $GCD(k, 0) = k$.

GCD(a, b) = a if b==0
            b if a==0
            GCD(a-b, b) if a>b
            GCD(a, b-a) otherwise

This algorithm again takes $O(max(a, b))$ time in worst case because if $b==1$, then, we have to call function $a$ times.

Based on Euclid’s theorem

Euclid simply stated that $GCD(a, b) = GCD(a\%b, b)$. Now, we will use Euclid’s theorem and the property $GCD(a, b) = GCD(b, a)$ to design an efficient algorithm for GCD. After performing $a\%b$, $a$ will become less than $b$ and hence, there is no point repeatedly calling $GCD(a, b) = GCD(a\%b, b)$. Hence, we will twist this relation a little bit to get our work done. Since $GCD(a\%b, b) = GCD(b, a\%b)$, we can say that $GCD(a, b) = GCD(b, a\%b)$ and now, we can repeatedly call this relation until second argument in $GCD()$ becomes $0$.

GCD(a, b) = a if b==0
            GCD(b, a%b) otherwise

So, were you able to guess the time complexity of this algorithm? I guess answer is no until you have a good background in algorithms. It might be hard to digest but the time complexity of this algorithm is $O(log(min(a, b)))$. I am not writing the proof here as it is pretty complex for a beginner and also you can read it online if you want to know more.
One more thing I would like to tell you is about the worst case of Euclid’s algorithm . In the worst case, $a$ and $b$ are consecutive terms of Fibonacci Sequence because performing $\%$ on consecutive Fibonacci numbers is equivalent to subtracting them which will result in another consecutive pair of Fibonacci numberrs. For example, $GCD(8, 5) = GCD(5, 8\%5) = GCD(5, 3) = GCD(5, 8-5)$. I have mentioned in my Fibonacci sequence post that we can find nth Fibonacci term in $O(log(n))$ time. You can also use this analogy to claim that Euclid algorithm runs in $O(log(n))$ time. So, enough of theoretical discussion, let’s write codes for these algorithms:

Code

#include <bits/stdc++.h>

using namespace std;

int gcdBruteForce(int a, int b) {
    int gcd = 1;
    for (int i=1; i<=min(a, b); i++) {
        if (a%i == 0 && b%i == 0) gcd = i;
    }
    return gcd;
}

int gcdSub(int a, int b) {
    if (a==0) return b;
    if (b==0) return a;
    
    if (a>b) return gcdSub(a-b, b);
    return gcdSub(a, b-a);
}

int gcdEuclid(int a, int b) {
    if (b==0) return a;
    return gcdEuclid(b, a%b);
}

int main() {
    
    cout << gcdBruteForce(8, 12) << "\n";
    cout << gcdSub(8, 12) << "\n";
    cout << gcdEuclid(8, 12) << "\n";
    
}

So, I have finished my work. Now, it is your turn to go to codechef or codeforces and search for problems with gcd tag and start solving them. Thank you guys for reading so far.
You can subscribe to my YouTube channel for video tutorials on competitive programming.
You can connect with me on LinkedIn. To get all of your queries answered, you can message me on Quora. Follow me on medium for more of my writings.

Leave a Reply

%d bloggers like this: