DSA problem
GCD / HCF of Two Numbers
Given two integers A and B, find their Greatest Common Divisor (GCD), also called the Highest Common Factor (HCF) - the largest integer that divides both without a remainder.
Brute force scans from min(A, B) down to 1, but Euclid's algorithm is far faster. It rests on the identity GCD(A, B) = GCD(B, A % B) with base case GCD(A, 0) = A: any common divisor of A and B must also divide A % B. Each step shrinks the numbers quickly, giving O(log(min(A, B))) time.
GCD is everywhere - simplifying fractions, computing LCM, modular arithmetic in cryptography, and the analysis of the Fibonacci sequence.
Examples
Example 1
Input:
A = 36, B = 60Output:
12Explanation: 12 is the largest number that divides both 36 and 60 exactly.
Constraints
- 1 <= A, B <= 10^9
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.