☕ DSA Java Articles

Topics › Basics › Know Basic Maths

GCD of Two Numbers

Easy TUF ID 372 A2Z

Java source ↗ Edit this article ↗

Problem

You are given two non-negative integers a and b. Return their greatest common divisor (GCD, also called HCF): the largest positive integer that divides both of them without remainder. By convention gcd(0, b) = b because every integer divides 0, and gcd(0, 0) = 0.

Constraints: 0 ≤ a, b ≤ 10^9.

Example 1

a = 20, b = 15
answer = 5          // divisors of 20: 1 2 4 5 10 20; of 15: 1 3 5 15; the largest common one is 5

Example 2

a = 7, b = 3
answer = 1          // the numbers are coprime

Example 3

a = 0, b = 9
answer = 9          // everything divides 0, so the answer is the other number

Approach 1: Brute force, try every candidate

Intuition. The GCD can be no larger than the smaller of the two numbers, so start at min(a, b) and walk downwards. The first value that divides both is, by construction, the greatest common divisor. Walking downward instead of upward lets us stop at the first hit.

Algorithm.

  1. If a == 0 return b; if b == 0 return a.
  2. For g from min(a, b) down to 1: if a % g == 0 and b % g == 0, return g.
  3. (Unreachable, since g = 1 always divides both.) Return 1.
static int bruteForce(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    for (int g = Math.min(a, b); g >= 1; g--) {
        if (a % g == 0 && b % g == 0) return g;
    }
    return 1;
}

Complexity. Time O(min(a, b)), which is 10^9 iterations for coprime inputs near the limit. Space O(1).

The final return 1 is only there because the compiler cannot prove the loop returns; 1 divides everything, so the loop always ends at g = 1 at the latest.

Approach 2: Better, Euclid by subtraction

Intuition. The key fact behind every fast GCD algorithm: if g divides both a and b, then it also divides a - b. Conversely anything dividing b and a - b divides their sum a. So the set of common divisors of (a, b) is the same as that of (a - b, b) when a > b, and therefore gcd(a, b) = gcd(a - b, b). Repeatedly subtract the smaller from the larger; the numbers shrink and, when they become equal, that common value is the GCD.

Algorithm.

  1. If a == 0 return b; if b == 0 return a.
  2. While a != b: if a > b set a = a - b, else set b = b - a.
  3. Return a.
static int better(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    while (a != b) {
        if (a > b) a -= b; else b -= a;
    }
    return a;
}

Dry run on a = 20, b = 15: (20, 15) -> (5, 15) -> (5, 10) -> (5, 5), return 5.

Complexity. Time O(max(a, b) / min(a, b)) subtractions per “round”, and in the worst case O(max(a, b)) overall: gcd(10^9, 1) performs almost a billion subtractions. Space O(1).

The zero checks are not optional here. Without them gcd(0, 9) would loop b -= 0 forever.

Subtraction is the right mental model, but notice that subtracting b from a over and over until the result drops below b is exactly what the remainder operation computes in one step. That observation gives the optimal algorithm.

Approach 3: Optimal, Euclid with modulo

Intuition. a % b is what remains after subtracting b from a as many times as possible, so gcd(a, b) = gcd(b, a % b). Each step replaces the pair (a, b) by (b, a % b), and the new second number is strictly smaller than b. It can be shown that the second number at least halves every two steps, so the number of steps is logarithmic.

The base case b == 0 returns a, which also covers gcd(a, 0) = a and gcd(0, 0) = 0 without special code. If a < b initially, the first step simply swaps them (a % b = a).

Algorithm.

  1. While b != 0: r = a % b, a = b, b = r.
  2. Return a.
static int optimal(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

Dry run on a = 20, b = 15:

a b a % b
20 15 5
15 5 0
5 0 stop, return 5

Complexity. Time O(log(min(a, b))): roughly 2 log2(min(a, b)) iterations, so at most about 60 for 32-bit inputs (the worst case is consecutive Fibonacci numbers). Space O(1).

The same algorithm reads even more naturally as a recursion, and the depth is the same logarithmic bound, so there is no stack-overflow risk:

static int optimalRecursive(int a, int b) {
    return b == 0 ? a : optimalRecursive(b, a % b);
}

Bonus: LCM from the GCD

The least common multiple satisfies lcm(a, b) * gcd(a, b) = a * b. Compute it as a / gcd * b, dividing first so the intermediate value stays small, and store the result in a long: lcm(100000, 99999) = 9999900000 does not fit in an int.

static long lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    return (long) (a / optimal(a, b)) * b;
}

Edge cases and pitfalls