Find GCD/HCF of Two Numbers - Java

Category: Medium | Concepts used: Loop-based checking, Euclidean algorithm

---

Problem Statement

Given two numbers, find their Greatest Common Divisor (GCD), also called Highest Common Factor (HCF) — the largest number that divides both evenly.

Input : 12, 18      Output: 6   (6 divides both 12 and 18)
Input : 7, 13         Output: 1    (co-prime numbers — only 1 divides both)

Examples (with edge scenarios)

#	a	b	Output	Why
1	12	18	6	Largest common divisor
2	7	13	1	Co-prime (no common factor besides 1)
3	0	5	5	By convention, GCD(0, n) = n
4	5	5	5	GCD of a number with itself is itself
5	-12	18	6	Typically, GCD is defined using absolute values — clarify if negatives should be handled

Common Fresher Mistake

Mistake	What happens	Fix
Using a brute-force loop checking every number from min(a,b) down to 1	Works, but slow for large numbers (O(min(a,b)) time)	Prefer the Euclidean algorithm — much faster, O(log(min(a,b)))
Not handling 0 as an input	May cause a divide-by-zero error in the Euclidean algorithm if not careful	Recall GCD(0, n) = n, and structure the base case accordingly

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether zero and negative values are allowed, how large the input can be, and what should happen when an arithmetic result exceeds the chosen Java type. The examples use the contract stated in this article, but an interview answer should say these assumptions aloud.

Analogy: Sizing Floor Tiles

Imagine you are a contractor trying to tile a rectangular floor of dimensions 12 ft by 18 ft using the largest possible square tiles that fit perfectly without any cutting:

• Solution 1 (Brute Force): You buy tiles of size 12x12 and try laying them. They don’t fit. You buy 11x11, then 10x10, checking every single size down to 1x1 until you find a size that divides both dimensions perfectly. This is slow and expensive.
• Solution 2 (Euclidean - Remainder Fitting):
  • You lay the largest possible square tiles based on the smaller dimension: a 12x12 tile on the 12x18 floor.
  • This leaves an uncovered rectangular section of 12 ft by 6 ft (where 18 % 12 = 6).
  • Now, the problem of tiling the entire floor simplifies to tiling this remaining 12x6 area!
  • You lay 6x6 tiles on the 12x6 area. They fit perfectly with no remainder (12 % 6 = 0).
  • Because 6 is the size that perfectly tiled the remaining remainder area, it is the greatest common divisor for the entire 12x18 floor!

---

Solution 1 — Brute Force (Check All Divisors)

Intuition

The most literal way to find the GCD is to test every number from the smaller of the two inputs down to 1, and return the first one that divides both a and b evenly — since we’re counting down, the first match we find is automatically the largest possible.

public class GCDBruteForce {
    public static int gcd(int a, int b) {
        int smaller = Math.min(a, b);

for (int i = smaller; i >= 1; i--) {
            if (a % i == 0 && b % i == 0) {
                return i; // largest number that divides both
            }
        }
        return 1; // fallback (technically 1 always divides both, so loop always finds something)
    }

public static void main(String[] args) {
        System.out.println(gcd(12, 18)); // 6
        System.out.println(gcd(7, 13));   // 1
    }
}

Output:

6
1

Dry Run (a=12, b=18)

smaller = min(12,18) = 12

i=12: 12%12=0, 18%12=6 -> not both divisible -> skip
i=11: 12%11=1 -> skip
...
i=6: 12%6=0, 18%6=0 -> BOTH divisible! -> return 6

Interviewer’s take

Correct, but inefficient — O(min(a,b)) time, which becomes slow for large numbers. Interviewers will almost certainly ask for the much faster, classic approach: the Euclidean algorithm.

Follow-up questions you might get:

• “Do you know a faster way to compute GCD?” → leads to Solution 2.

---

Solution 2 — Euclidean Algorithm (Recursive, Recommended)

Intuition

The Euclidean algorithm relies on a key mathematical fact: GCD(a, b) = GCD(b, a % b). In plain words — the GCD of two numbers doesn’t change if you replace the larger number with the remainder of dividing it by the smaller one. Repeating this shrinks the numbers rapidly (much faster than counting down one at a time) until one of them becomes 0 — at which point the other number IS the GCD.

public class GCDEuclidean {
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a; // base case: GCD(a, 0) = a
        }
        return gcd(b, a % b); // recursive case
    }

public static void main(String[] args) {
        System.out.println(gcd(12, 18)); // 6
        System.out.println(gcd(7, 13));   // 1
        System.out.println(gcd(0, 5));      // 5
    }
}

Output:

6
1
5

Dry Run (a=12, b=18)

gcd(12, 18) = gcd(18, 12%18=12)     [note: order swaps naturally when a < b]
gcd(18, 12) = gcd(12, 18%12=6)
gcd(12, 6)  = gcd(6, 12%6=0)
gcd(6, 0)   = 6   (base case: b==0, return a)

Final: 6

Interviewer’s take

This is the gold-standard answer — the Euclidean algorithm is one of the oldest and most efficient algorithms known (dating back over 2000 years!), running in O(log(min(a,b))) time — dramatically faster than the brute-force approach, especially for large numbers. Knowing this by name and being able to derive/explain it is a strong signal.

Follow-up questions you might get:

• “Why does GCD(a, b) = GCD(b, a % b) hold true?” → Any number that divides both a and b must also divide their difference (and, by extension, the remainder of a divided by b) — so the set of common divisors of (a, b) is exactly the same as the set of common divisors of (b, a % b), meaning their GCDs must be equal too.
• “Can you write this iteratively instead of recursively?” → leads to Solution 3.
• “How does HCF relate to LCM?” → LCM(a, b) = (a * b) / GCD(a, b) — a common, very related follow-up problem.

---

Solution 3 — Euclidean Algorithm (Iterative Version)

Intuition

Same core idea as Solution 2, just using a loop instead of recursive calls — repeatedly replace (a, b) with (b, a % b) until b becomes 0.

public class GCDEuclideanIterative {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

public static void main(String[] args) {
        System.out.println(gcd(12, 18)); // 6
    }
}

Output:

6

Interviewer’s take

Functionally identical to the recursive version, just avoiding call-stack usage (O(1) space instead of O(log(min(a,b))) stack frames). A nice trade-off to mention, though both are considered excellent answers.

---

📊 Visual Flowchart

graph TD
    Start["Input: a, b"] --> CheckZero{"b == 0?"}
    CheckZero -->|Yes| RetA["Return a"]
    CheckZero -->|No| Recurse["Calculate rem = a % b<br>Call gcd(b, rem)"]
    Recurse --> CheckZero

---

Final Verdict — Which Solution Should You Give?

Solution 1 (brute force)  ──O(min(a,b))──►  Fine to start, but flag inefficiency
Solution 2/3 (Euclidean algorithm)  ──O(log(min(a,b)))──►   THE EXPECTED, CLASSIC ANSWER

• The Euclidean algorithm (recursive or iterative) is essential to know — this is one of the most fundamental algorithms in computer science and math, and interviewers expect familiarity with it, not just brute force.

---

Quick Recap

Approach	Time	Space	Interview Signal
Brute force	O(min(a,b))	O(1)	Correct, but needs optimization
Euclidean (recursive)	O(log(min(a,b)))	O(log(min(a,b))) call stack	Classic, expected
Euclidean (iterative)	O(log(min(a,b)))	O(1)	Classic, most space-efficient