easyNumber ProblemsJava

Find the GCD of Two Numbers Using the Euclidean Algorithm

Compute the greatest common divisor of two integers with the Euclidean algorithm.

Quick Answer

The Euclidean algorithm says gcd(a, b) = gcd(b, a mod b). Repeatedly replace the pair (a, b) with (b, a mod b) until b becomes 0; the remaining a is the greatest common divisor. This is far faster than testing every candidate divisor.

Problem Statement

The greatest common divisor (GCD) of two integers is the largest number that divides both without a remainder. The Euclidean algorithm finds it quickly using the fact that gcd(a, b) = gcd(b, a mod b).

Given two integers, return their GCD. Repeatedly replace the pair with the divisor and the remainder until the remainder is 0; the last non-zero divisor is the GCD. Work with absolute values so negative inputs behave correctly.

Input: Two integers a and b.

Output: The greatest common divisor of a and b.

Examples

Example 1
Input:  48, 18
Output: 6

48 mod 18 = 12, 18 mod 12 = 6, 12 mod 6 = 0, so the GCD is 6.

Example 2
Input:  17, 5
Output: 1

17 and 5 share no factor other than 1, so they are coprime and the GCD is 1.

Constraints

  • a and b fit in a 32-bit int; treat their absolute values
  • gcd(x, 0) is defined as |x|

Think Before You Code

Reveal the questions to ask yourself first
  • Why is gcd(a, b) the same as gcd(b, a mod b)?
  • When does the loop stop, and what value holds the answer at that point?
  • How should negative inputs be handled?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
The key identity is gcd(a, b) = gcd(b, a mod b); apply it repeatedly.
Hint 2
Loop while b is not 0, each time setting a to b and b to the old a mod b.
Hint 3
When b reaches 0, the current a is the answer; take absolute values first for negatives.

Approach

Reveal the step-by-step approach

Repeatedly reduce the pair using remainders.

  1. Replace a and b with their absolute values.
  2. While b is not 0:
    • Remember temp = b.
    • Set b = a % b.
    • Set a = temp.
  3. Return a, which now holds the GCD.

Each step shrinks the numbers quickly because the remainder is always smaller than the divisor, so the loop terminates fast.

Dry Run

Walk through the example step by step

Computing gcd(48, 18):

a  | b  | a % b
---+----+------
48 | 18 | 12
18 | 12 | 6
12 | 6  | 0
6  | 0  | stop

When b becomes 0, a = 6 is the GCD.

Solution

Reveal the full Java solution
public class GcdEuclidean {
    public static int gcd(int a, int b) {
        a = Math.abs(a);
        b = Math.abs(b);
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

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

Any common divisor of a and b also divides a % b, so replacing a with the remainder never loses the GCD while making the numbers smaller. The loop ends when b hits 0, at which point a is the greatest common divisor. Taking absolute values up front makes the routine correct for negative inputs.

Time: O(log(min(a, b)))Space: O(1)

Common Mistakes

  • Swapping a and b incorrectly and losing the remainder, breaking the reduction.
  • Not handling gcd(x, 0), which should return |x| rather than looping forever.

Edge Cases to Test

  • gcd(x, 0) returns |x| because the loop never runs.
  • Negative inputs work once you take absolute values first.

Interview Follow-Ups

  • How would you use the GCD to compute the LCM of the same two numbers?
  • How would you write the Euclidean algorithm recursively?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us