Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Greatest Common Divisor of 2 numbers

EASYProblemSolveExternal Links

Description

Given two positive integers a and b, find their Greatest Common Divisor (GCD).

The GCD (also called Highest Common Factor or HCF) of two numbers is the largest positive integer that divides both numbers without leaving a remainder.

For instance, the divisors of 20 are {1, 2, 4, 5, 10, 20} and the divisors of 28 are {1, 2, 4, 7, 14, 28}. The common divisors are {1, 2, 4}, and the greatest among them is 4. So GCD(20, 28) = 4.

The GCD is a fundamental concept in number theory and appears frequently in real-world scenarios:

  • Simplifying fractions: To reduce 12/18 to lowest terms, divide both by GCD(12, 18) = 6, giving 2/3
  • Computing LCM: LCM(a, b) = (a × b) / GCD(a, b)
  • Cryptography: The Extended Euclidean Algorithm (built on GCD) is used in RSA encryption

Note: Do not use any built-in GCD function.

Examples

Example 1

Input: a = 20, b = 28

Output: 4

Explanation: The divisors of 20 are {1, 2, 4, 5, 10, 20}. The divisors of 28 are {1, 2, 4, 7, 14, 28}. The common divisors are {1, 2, 4}. The largest common divisor is 4, so GCD(20, 28) = 4.

Example 2

Input: a = 60, b = 36

Output: 12

Explanation: The divisors of 60 are {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}. The divisors of 36 are {1, 2, 3, 4, 6, 9, 12, 18, 36}. The common divisors are {1, 2, 3, 4, 6, 12}. The largest is 12, so GCD(60, 36) = 12.

Example 3

Input: a = 17, b = 13

Output: 1

Explanation: 17 and 13 are both prime numbers. The only positive integer that divides both is 1, so GCD(17, 13) = 1. When GCD equals 1, the numbers are called coprime (or relatively prime).

Example 4

Input: a = 8, b = 0

Output: 8

Explanation: Every integer divides 0 (since 0 = k × 0 for any k), so the GCD of any number with 0 is that number itself. GCD(8, 0) = 8. This is an important edge case and also the base case for the Euclidean algorithm.

Constraints

  • 1 ≤ a, b ≤ 10^9

Editorial

Brute Force

Intuition

The most straightforward way to find the GCD follows directly from its definition: check every possible divisor and keep the largest one that divides both numbers.

Imagine you have two ropes of lengths 20 and 28, and you want to cut them into the longest possible equal-length pieces with no leftover rope. You would try every possible piece length starting from the smallest: can I cut both ropes into 1-unit pieces? Yes. 2-unit pieces? Yes. 3-unit? No (20 ÷ 3 leaves a remainder). 4-unit? Yes. And so on, up to the smaller rope length. The largest piece length that works for both ropes is the GCD.

We iterate from 1 to min(a, b), and for each number, we check if it divides both a and b. If it does, we update our answer. At the end, the last (largest) value that divided both is the GCD.

Step-by-Step Explanation

Let's trace through with a = 20, b = 28:

Step 1: Initialize gcd = 1 (since 1 always divides any positive integer).

Step 2: Start checking from i = 1 up to min(20, 28) = 20.

Step 3: i = 1: Does 1 divide 20? Yes (20 % 1 = 0). Does 1 divide 28? Yes (28 % 1 = 0). Update gcd = 1.

Step 4: i = 2: Does 2 divide 20? Yes (20 % 2 = 0). Does 2 divide 28? Yes (28 % 2 = 0). Update gcd = 2.

Step 5: i = 3: Does 3 divide 20? No (20 % 3 = 2). Skip.

Step 6: i = 4: Does 4 divide 20? Yes (20 % 4 = 0). Does 4 divide 28? Yes (28 % 4 = 0). Update gcd = 4.

Step 7: i = 5: Does 5 divide 20? Yes (20 % 5 = 0). Does 5 divide 28? No (28 % 5 = 3). Skip.

Step 8: i = 6 through 9: None divide both 20 and 28.

Step 9: i = 10: Does 10 divide 20? Yes. Does 10 divide 28? No (28 % 10 = 8). Skip.

Step 10: i = 11 through 20: None divide both. Loop ends.

Result: gcd = 4.

Brute Force — Checking All Divisors from 1 to min(a, b) — Watch as we test every integer from 1 to 20 to see if it divides both 20 and 28. Each successful common divisor updates our answer.

Algorithm

  1. Initialize gcd = 1
  2. For every integer i from 1 to min(a, b):
    • If a % i == 0 AND b % i == 0, update gcd = i
  3. Return gcd

Code

#include <iostream>
#include <algorithm>
using namespace std;

class Solution {
public:
    int gcd(int a, int b) {
        int result = 1;
        int limit = min(a, b);
        
        for (int i = 1; i <= limit; i++) {
            if (a % i == 0 && b % i == 0) {
                result = i;
            }
        }
        
        return result;
    }
};
class Solution:
    def gcd(self, a: int, b: int) -> int:
        result = 1
        limit = min(a, b)
        
        for i in range(1, limit + 1):
            if a % i == 0 and b % i == 0:
                result = i
        
        return result
class Solution {
    public int gcd(int a, int b) {
        int result = 1;
        int limit = Math.min(a, b);
        
        for (int i = 1; i <= limit; i++) {
            if (a % i == 0 && b % i == 0) {
                result = i;
            }
        }
        
        return result;
    }
}

Complexity Analysis

Time Complexity: O(min(a, b))

We iterate from 1 to min(a, b), performing a constant-time modulus operation at each step. The total work is proportional to the smaller of the two numbers.

Space Complexity: O(1)

We only use a few integer variables (result, limit, i). No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force checks every integer from 1 to min(a, b). With the constraint that a and b can be up to 10^9, the loop could run up to one billion iterations. Even at 10^8 operations per second, this would take roughly 10 seconds — far beyond the typical 1-2 second time limit.

The fundamental problem is that we are checking many numbers that cannot possibly be the GCD. For instance, if we already know that 4 divides both numbers, there is no point checking 5, 6, or 7 — we need to look for multiples of 4, or better yet, use a mathematical property that drastically reduces the search space.

The key mathematical insight is: GCD(a, b) = GCD(b, a mod b). This means instead of trying every candidate divisor, we can repeatedly replace the larger number with the remainder, reducing the problem size exponentially. This is the Euclidean Algorithm, and it reduces the number of steps from O(min(a, b)) to O(log(min(a, b))).

Better Approach - Subtraction-Based (Euclid's Original)

Intuition

Euclid's original algorithm is based on a simple but powerful observation: if a number d divides both a and b, then d also divides (a - b).

Why? If d divides a, then a = d × p for some integer p. If d divides b, then b = d × q for some integer q. So a - b = d × (p - q), which means d divides (a - b) as well.

This means the set of common divisors of (a, b) is the same as the set of common divisors of (a - b, b). Therefore, their greatest common divisor is the same: GCD(a, b) = GCD(a - b, b) when a > b.

The algorithm repeatedly subtracts the smaller number from the larger one. Each subtraction preserves the GCD while making the numbers closer to each other. When both numbers become equal, that value is the GCD.

Think of it like this: you have two stacks of blocks, one with 20 blocks and one with 28 blocks. You keep removing a stack-sized chunk from the taller stack. Eventually both stacks are the same height — that height is the GCD.

Step-by-Step Explanation

Let's trace GCD(48, 18) using repeated subtraction:

Step 1: a = 48, b = 18. Since a > b, replace a with a - b = 48 - 18 = 30.

Step 2: a = 30, b = 18. Since a > b, replace a with a - b = 30 - 18 = 12.

Step 3: a = 12, b = 18. Since b > a, replace b with b - a = 18 - 12 = 6.

Step 4: a = 12, b = 6. Since a > b, replace a with a - b = 12 - 6 = 6.

Step 5: a = 6, b = 6. Both are equal! GCD = 6.

Subtraction-Based GCD — Repeated Subtraction Until Equal — Watch how we repeatedly subtract the smaller value from the larger one. The pair shrinks at each step while the GCD is preserved, until both values converge to the answer.

Algorithm

  1. While a ≠ b:
    • If a > b, replace a with a - b
    • Else, replace b with b - a
  2. When a == b, return a (this is the GCD)

Code

#include <iostream>
using namespace std;

class Solution {
public:
    int gcd(int a, int b) {
        while (a != b) {
            if (a > b) {
                a = a - b;
            } else {
                b = b - a;
            }
        }
        return a;
    }
};
class Solution:
    def gcd(self, a: int, b: int) -> int:
        while a != b:
            if a > b:
                a = a - b
            else:
                b = b - a
        return a
class Solution {
    public int gcd(int a, int b) {
        while (a != b) {
            if (a > b) {
                a = a - b;
            } else {
                b = b - a;
            }
        }
        return a;
    }
}

Complexity Analysis

Time Complexity: O(max(a, b)) in the worst case

When one number is much larger than the other — for example GCD(1000000, 1) — the algorithm subtracts 1 repeatedly, requiring 999,999 steps. In general, the worst case occurs when a and b are consecutive Fibonacci numbers, leading to the maximum number of subtractions.

Space Complexity: O(1)

Only two variables (a and b) are modified in place. No additional data structures needed.

Why This Approach Is Not Efficient

While the subtraction method is mathematically elegant, it can be extremely slow when the two numbers differ greatly. Consider GCD(1,000,000,000, 1): the algorithm would perform 999,999,999 subtractions — practically the same as brute force.

The root cause is that repeated subtraction of the same value is just slow division. If a = 48 and b = 18, we subtract 18 from 48 twice to get 12. But that is exactly the same as computing 48 mod 18 = 12 in a single operation!

This leads to the key optimization: replace subtraction with the modulus (%) operator. Instead of subtracting b from a many times, compute a % b directly. This one change transforms the worst case from O(max(a, b)) to O(log(min(a, b))) — an exponential improvement.

Optimal Approach - Euclidean Algorithm (Division-Based)

Intuition

The Euclidean Algorithm is one of the oldest known algorithms — described by Euclid around 300 BCE — and it remains one of the most elegant and efficient.

The core insight is the same as the subtraction method, but turbocharged: GCD(a, b) = GCD(b, a mod b).

Why does this work? The modulus operation a mod b gives the remainder when a is divided by b. Mathematically, a = q × b + r, where r = a mod b. Any number that divides both a and b must also divide r (because r = a - q × b). And any number that divides both b and r must also divide a (because a = q × b + r). So the set of common divisors of (a, b) is identical to the set of common divisors of (b, r). Their GCD is the same.

The algorithm repeatedly replaces the pair (a, b) with (b, a mod b). Since the remainder is always strictly smaller than b, the values shrink rapidly. When b becomes 0, the current value of a is the GCD.

Think of the modulus as doing all the subtractions at once. Where the subtraction method subtracts b from a one at a time, modulus jumps straight to the final remainder. This makes the algorithm logarithmic — each step roughly halves the size of the numbers.

Step-by-Step Explanation

Let's trace GCD(48, 18) using the Euclidean Algorithm:

Step 1: a = 48, b = 18. Compute 48 mod 18 = 12 (because 48 = 2 × 18 + 12). Replace: a = 18, b = 12.

Step 2: a = 18, b = 12. Compute 18 mod 12 = 6 (because 18 = 1 × 12 + 6). Replace: a = 12, b = 6.

Step 3: a = 12, b = 6. Compute 12 mod 6 = 0 (because 12 = 2 × 6 + 0). Replace: a = 6, b = 0.

Step 4: b = 0. The algorithm terminates. GCD = a = 6.

Only 3 mod operations! Compare this to the subtraction method (4 steps) and brute force (18 checks). For large numbers, the difference is dramatic — GCD(10^9, 1) takes just 1 step with modulus, but 10^9 steps with subtraction.

Euclidean Algorithm — GCD via Modulus — Watch how the Euclidean Algorithm rapidly reduces the problem size using the modulus operator. Each step replaces (a, b) with (b, a mod b) until the remainder hits zero.

Algorithm

Iterative version:

  1. While b ≠ 0:
    • Compute temp = b
    • Set b = a mod b
    • Set a = temp
  2. Return a

Recursive version:

  1. Base case: if b == 0, return a
  2. Recursive case: return GCD(b, a mod b)

Code

#include <iostream>
using namespace std;

class Solution {
public:
    // Iterative version
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // Recursive version
    int gcdRecursive(int a, int b) {
        if (b == 0) return a;
        return gcdRecursive(b, a % b);
    }
};
class Solution:
    # Iterative version
    def gcd(self, a: int, b: int) -> int:
        while b != 0:
            a, b = b, a % b
        return a
    
    # Recursive version
    def gcd_recursive(self, a: int, b: int) -> int:
        if b == 0:
            return a
        return self.gcd_recursive(b, a % b)
class Solution {
    // Iterative version
    public int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    // Recursive version
    public int gcdRecursive(int a, int b) {
        if (b == 0) return a;
        return gcdRecursive(b, a % b);
    }
}

Complexity Analysis

Time Complexity: O(log(min(a, b)))

This is the critical advantage of the Euclidean Algorithm. At each step, the remainder a mod b is strictly less than b. In fact, it can be proven that after every two consecutive steps, the smaller number is reduced by at least half. This means the algorithm terminates in at most 2 × log₂(min(a, b)) steps.

For a, b up to 10^9, that is at most about 2 × 30 = 60 steps — compared to up to 10^9 for brute force.

The worst case occurs when a and b are consecutive Fibonacci numbers (e.g., GCD(89, 55)), which requires the maximum number of steps. This is because Fibonacci numbers produce quotients of 1 at every step, so the values decrease as slowly as possible.

Space Complexity:

  • Iterative: O(1) — only a few variables
  • Recursive: O(log(min(a, b))) — due to the recursion stack depth, which equals the number of recursive calls