GCD of Two Numbers
Updated Jan 31, 2026
Problem
Given two positive integers a and b, find their Greatest Common Divisor (GCD).
The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder.
Input: Two space-separated integers a and b.
Output: Their GCD.
Constraints
1 <= a, b <= 10^9
Follow Up
Can you solve this efficiently using the Euclidean algorithm?
Examples
Example 1
Input:
a = 12, b = 18
Output:
6
Example 2
Input:
a = 7, b = 11
Output:
1
7 and 11 are coprime.
Example 3
Input:
a = 100, b = 25
Output:
25
Function Signature
def gcd(self, a: int, b: int) -> int
How to Submit
Implement a Solution class with a gcd method.
Your method will be called with the input parameters and should return the answer.