mediumBasic Math Concepts

GCD or HCF

Find the greatest positive integer that divides both a and b.

GeeksforGeeks ↗

Work through the cases

3 examples

Input notation

Two positive integers, each at most 1000000000.

Expected result

Their greatest common divisor.

Case 1

Input

24 36

Expected output

Case 2

Input

17 9

Expected output

Case 3

Input

9 9

Expected output

These notes use simplified input/output notation. The linked platform defines the method signature and judge format.

FROM IDEA TO IMPLEMENTATION

Understand the approach.

Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.

Repeatedly replace the pair with the second value and the remainder. The final nonzero value is the GCD. Time: O(log min(a,b)); extra space: O(1).

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        ArrayList<Long> values = new ArrayList<>();
        while (in.hasNextLong()) values.add(in.nextLong());
        long[] a = values.stream().mapToLong(Long::longValue).toArray();
        long n = a[0];
        long x = a[0], y = a[1]; while (y != 0) { long r = x % y; x = y; y = r; } System.out.println(x);
    }
}

Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.