Given two integers a and b, find their GCD using the Euclidean Algorithm. The GCD of two numbers is the largest positive integer that divides both numbers exactly.
Example 1
Input: a = 48, b = 18
Output: 6
Explanation: The common divisors of 48 and 18 are 1, 2, 3, 6, and the greatest among them is 6.
Example 2
Input: a = 42, b = 56
Output: 14
Explanation: 14 divides both 42 and 56, and no larger common divisor exists.
Brute Force Approach
The first thought can be completely direct. Any common divisor of a and b must be less than or equal to the smaller of the two numbers. So one simple way is to test every number from 1 to min(a, b) and keep track of the largest value that divides both numbers.
This is not the fastest method, but it helps in understanding what the answer really means. Before using Euclid's observation, it is helpful to first see the problem in this plain and concrete form.
Algorithm
First, make both numbers non-negative by taking their absolute values. This is done because the GCD is based on divisibility, and the sign does not change the answer.
If both numbers become
0, return0in this implementation. Mathematically,gcd(0, 0)is undefined, but in programming this special return is often used to keep the function safe.Find the smaller of the two numbers, because no common divisor can be larger than that value.
Check every number from
1to that smaller value. Each number is tested because it might be a divisor of both values.Whenever a number divides both inputs exactly, store it as the current answer. This update matters because the loop moves from small to large values, so the latest valid divisor is always the largest seen so far.
After the loop finishes, return the stored answer because all possible common divisors have already been checked.
Dry Run
Calculate GCD
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Finds the GCD by checking every number from 1 to the smaller input value. */ int gcdBruteForce(int a, int b) { // Convert both numbers to non-negative values first. a = abs(a); b = abs(b); // Return 0 here so the undefined 0,0 case stays safe in code. if (a == 0 && b == 0) { return 0; } // The GCD cannot be larger than the smaller number. int limit = min(a, b); // Stores the largest common divisor found so far. int answer = 1; // When one number is 0, the other number itself is the GCD. if (limit == 0) { return max(a, b); } for (int i = 1; i <= limit; i++) { // Update the answer only when i divides both numbers exactly. if (a % i == 0 && b % i == 0) { answer = i; } } return answer; }};// Driver code startsint main() { int a = 48; int b = 18; Solution obj; cout << obj.gcdBruteForce(a, b) << endl; return 0;}Complexity Analysis
Time Complexity: O(min(a, b)), because every number from 1 to the smaller value is checked.
Space Complexity: O(1), because constant space is used.
Optimal Approach
The subtraction idea becomes even better after one more observation. Repeatedly subtracting b from a is doing the same work as taking a % b, just in one jump.
For example, if a = 48 and b = 18, then repeated subtraction would go 48 -> 30 -> 12. The final leftover after removing as many 18s as possible is exactly 48 % 18 = 12.
That is why the Euclidean Algorithm is usually written as:
gcd(a, b) = gcd(b, a % b)
This matters because the numbers shrink much faster. Instead of removing one copy at a time, the modulo operation removes all full copies in one step. That is the reason this version is the standard and optimal approach for most coding problems.
Algorithm
First, convert both numbers to non-negative values because the sign does not affect the GCD.
If both numbers are
0, return0in this implementation so the function stays safe for all inputs.While
bis not0, keep reducing the pair. The process continues because as long as a remainder exists, the final GCD has not been reached yet.Store the current value of
bin a temporary variable before updating anything. This is needed because the next pair must become(b, a % b).Replace
bwitha % b, because the GCD of(a, b)is the same as the GCD of(b, a % b).Move the old value of
bintoa, because that old divisor becomes the first number of the next step.When
bbecomes0, returnabecause the last non-zero value is the GCD.
Dry Run
Euclidean Algorithm Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Finds the GCD by applying the modulo-based Euclidean Algorithm iteratively. */ int gcdEuclidean(int a, int b) { // Convert both numbers to non-negative values first. a = abs(a); b = abs(b); // Return 0 here so the undefined 0,0 case stays safe in code. if (a == 0 && b == 0) { return 0; } while (b != 0) { // Store the current divisor before updating the pair. int temp = b; // The remainder becomes the next smaller subproblem. b = a % b; // Move the old divisor into a for the next iteration. a = temp; } return a; }};// Driver code startsint main() { int a = 48; int b = 18; Solution obj; cout << obj.gcdEuclidean(a, b) << endl; return 0;}Complexity Analysis
Time Complexity: O(log(min(a, b))), because the numbers shrink quickly after each modulo operation.
Space Complexity: O(1), because constant space is used.
Interview follow-up Questions
Because any number that divides both a and b will also divide the remainder left after dividing a by b. So the common divisors do not change, only the numbers become smaller.
Be the first to add a comment.