Find the GCD of Two Numbers
Solve this ProblemEasy10 min
Topics
BasicsLoopsRecursionMath
Companies
TCSInfosysWipro
Given two positive integers
a and b, return their greatest common divisor (GCD) — the largest number that divides both evenly.
The brute-forceBrute ForceChecking every candidate from min(a, b) down to 1, stopping at the first one that divides both numbers. approach checks candidates one at a time, which is simple but can take as many as min(a, b) steps. The Euclidean algorithmEuclidean AlgorithmRepeatedly replacing (a, b) with (b, a % b) — since any common divisor of a and b also divides a % b — until b reaches 0., one of the oldest algorithms in existence, shrinks the pair of numbers geometrically fast instead, usually finishing in a handful of rounds even for huge inputs.
Test Case 1:
Input:a = 12, b = 18
Output:6
Explanation:6 is the largest number that divides both 12 and 18.
Test Case 2:
Input:a = 7, b = 13
Output:1
Explanation:7 and 13 share no common factor besides 1.
Test Case 3:
Input:a = 20, b = 20
Output:20
Explanation:A number is always its own GCD with itself.
Constraints
- ◆
1 ≤ a ≤ 1000000 - ◆
1 ≤ b ≤ 1000000
Try the Dry Run
Approach & Solutions
Brute Force — Check Every Candidate DownwardBrute
The GCD can never be larger than the smaller of the two numbers. So start at min(a, b) and count downward, checking each candidate against both a and b — the first one that divides both evenly is the greatest common divisor.
Time
O(min(a, b))Space
O(1)Java
1class Solution {
2 public int findGCD(int a, int b) {
3 int smaller = Math.min(a, b);
4 for (int i = smaller; i >= 1; i--) {
5 if (a % i == 0 && b % i == 0) {
6 return i;
7 }
8 }
9 return 1;
10 }
11}Euclidean AlgorithmOptimal
Any common divisor of a and b also divides their remainder, a % b — so gcd(a, b) equals gcd(b, a % b). Repeat that swap-and-mod step, and the pair shrinks fast (far faster than counting down one at a time) until b finally reaches 0, at which point a holds the answer.
Time
O(log(min(a, b)))Space
O(1)Java
1class Solution {
2 public int findGCD(int a, int b) {
3 while (b != 0) {
4 int temp = b;
5 b = a % b;
6 a = temp;
7 }
8 return a;
9 }
10}