Given two integers a and b, find their GCD and LCM.
The GCD, or Greatest Common Divisor, is the largest positive integer that divides both numbers exactly. The LCM, or Least Common Multiple, is the smallest positive integer that is divisible by both numbers.
Example 1
Input: a = 12, b = 18
Output: gcd = 6, lcm = 36
Explanation: The common divisors of 12 and 18 are 1, 2, 3, and 6, so the GCD is 6. The smallest number divisible by both 12 and 18 is 36, so the LCM is 36.
Example 2
Input: a = 8, b = 20
Output: gcd = 4, lcm = 40
Explanation: The common divisors of 8 and 20 are 1, 2, and 4, so the GCD is 4. The smallest common multiple of 8 and 20 is 40.
Brute Force Approach
The first observation is very direct: a common divisor of two numbers cannot be greater than the smaller number. So if the goal is to find the GCD, one simple way is to check all possible divisors up to min(a, b).
For LCM, the thought goes in the opposite direction. A common multiple must be a number that both a and b can divide exactly. So starting from the larger number and checking upward will eventually reach the first common multiple, which is the LCM.
Algorithm
First, work with the absolute values of
aandb, because GCD and LCM are usually discussed using non-negative values.To find the GCD, check every number from
1tomin(a, b)and keep updating the answer whenever a number divides both values exactly. The last valid common divisor found this way will be the greatest one.To find the LCM, start from
max(a, b)and keep moving upward until a number is found that is divisible by bothaandb. That first valid value is the least common multiple.Return both answers after the two searches finish.
Key Points
If one number is
0and the other is non-zero, the GCD is the non-zero number and the LCM is0.If both numbers are
0, GCD and LCM are usually treated as0in programming problems to keep the behavior simple and consistent.
Dry Run
GCD and LCM Brute Force Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the GCD and LCM of two numbers by directly checking divisors and multiples. */ pair<int, int> findGcdLcm(int a, int b) { // Work with non-negative values for divisor logic. a = abs(a); b = abs(b); // Handle the fully zero case before normal processing. if (a == 0 && b == 0) { return {0, 0}; } // Handle cases where one value is zero. if (a == 0 || b == 0) { return {max(a, b), 0}; } // Stores the best common divisor found so far. int gcdValue = 1; int limit = min(a, b); for (int i = 1; i <= limit; i++) { // Update the GCD whenever a better common divisor is found. if (a % i == 0 && b % i == 0) { gcdValue = i; } } // Start from the larger value because the LCM cannot be smaller than that. int lcmValue = max(a, b); while (true) { // Stop at the first value divisible by both numbers. if (lcmValue % a == 0 && lcmValue % b == 0) { break; } lcmValue++; } return {gcdValue, lcmValue}; }};// Driver code startsint main() { int a = 12; int b = 18; Solution obj; pair<int, int> result = obj.findGcdLcm(a, b); cout << "gcd = " << result.first << ", lcm = " << result.second << endl; return 0;}Complexity Analysis
Time Complexity: O(min(a, b) + lcm(a, b)) in the worst case for this direct implementation, because the GCD search checks up to the smaller number and the LCM search may continue upward until the first common multiple is reached.
Space Complexity: O(1), because only a few variables are used.
Optimal Approach
The key observation for GCD is that the common divisors of two numbers do not change when the larger number is replaced by the remainder after division. For example, gcd(18, 12) becomes gcd(12, 6), and then gcd(6, 0), so the answer is 6.
Once the GCD is known, the LCM no longer needs a separate search. The important relation is gcd(a, b) * lcm(a, b) = |a * b|. That means the LCM can be found directly from the GCD, which makes the full solution much faster and cleaner.
Algorithm
First, work with the absolute values of
aandb, because GCD and LCM are normally taken as non-negative results.Use the Euclidean algorithm to compute the GCD. Repeatedly replace
(a, b)with(b, a % b)untilbbecomes0. At that point,astores the GCD.Handle the zero case carefully before computing the LCM. If either number is
0, the LCM should be0because0is the only common multiple in that situation.For non-zero numbers, compute the LCM using
lcm = (a / gcd) * b. This form is preferred because it avoids making the intermediate multiplication larger than needed.Return both the GCD and LCM after the values are fully computed.
Key Points
If one number is
0and the other is non-zero, the GCD is the non-zero number and the LCM is0.If both numbers are
0, this article treats both GCD and LCM as0to keep the programming behavior consistent.
Dry Run
GCD and LCM Optimal Dry Run
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: /* Returns the GCD and LCM of two numbers by using the Euclidean algorithm. */ pair<int, int> findGcdLcm(int a, int b) { /* Work with non-negative values for divisor logic. */ a = abs(a); b = abs(b); /* Handle the fully zero case before normal processing. */ if (a == 0 && b == 0) { return {0, 0}; } /* Store the cleaned values because a and b will change during GCD computation. */ int originalA = a; int originalB = b; /* Repeatedly reduce the pair until the second value becomes zero. */ while (b != 0) { /* Store the remainder because it becomes the next second value. */ int remainder = a % b; /* Shift the current second value into the first position. */ a = b; /* Move the remainder into the second position for the next step. */ b = remainder; } /* Store the final GCD after Euclid's process finishes. */ int gcdValue = a; /* Handle the LCM separately when one original number was zero. */ if (originalA == 0 || originalB == 0) { return {gcdValue, 0}; } /* Compute the LCM from the GCD using a safer multiplication order. */ int lcmValue = (originalA / gcdValue) * originalB; return {gcdValue, lcmValue}; }};// Driver code startsint main() { int a = 12; int b = 18; Solution obj; pair<int, int> result = obj.findGcdLcm(a, b); cout << "gcd = " << result.first << ", lcm = " << result.second << endl; return 0;}Complexity Analysis
Time Complexity: O(log(min(a, b))), because in each step the pair becomes much smaller by replacing the larger number with a remainder. That remainder is always smaller than the current second number, so the values shrink fast instead of decreasing one by one. Because the size keeps dropping in this way, only a logarithmic number of steps is needed.
Space Complexity: O(1), because only a constant number of variables are used.
Interview follow-up Questions
For two non-zero numbers, the relation gcd(a, b) * lcm(a, b) = |a * b| connects them directly. Once the GCD is known, the LCM follows immediately.
Be the first to add a comment.