246. Greatest Common Divisor and LCM
Problem
Return (gcd,lcm) for any two integers a and b, using nonnegative results. Define gcd(0,0)=0 and lcm(a,0)=0. Implement Euclid's algorithm directly; compute LCM after dividing by GCD to reduce intermediate magnitude.
Examples
Example 1
gcd_lcm(48,18)
=> (6, 144)Euclid preserves common divisors while shrinking the second operand.
Example 2
gcd_lcm(-6,8)
=> (2, 24)Results are normalized to nonnegative magnitudes.
Example 3
gcd_lcm(0,0)
=> (0, 0)The explicit zero convention avoids division by zero.
Reveal the worked solution and reasoning
Why this mechanism works
A divisor common to a and b is also common to b and a mod b, and the converse holds. Repeatedly replace the pair with that smaller equivalent problem until the second value is zero. Normalize signs first. For nonzero inputs, gcd*lcm=abs(a*b).
State and boundaries
The current pair has the same GCD as the original magnitudes. saved_a and saved_b retain those magnitudes for the later LCM calculation.
Protocol
- Take absolute values and save them.
- While b is nonzero replace (a,b) with (b,a%b).
- The remaining a is the GCD.
- Return LCM zero if either original was zero.
- Otherwise compute (saved_a//gcd)*saved_b.
Visualization
gcd(48,18): (48,18)->(18,12)->(12,6)->(6,0)
gcd=6; lcm=(48//6)*18=144Python implementation
def gcd_lcm(a, b):
saved_a, saved_b = abs(a), abs(b)
a, b = saved_a, saved_b
while b:
a, b = b, a % b
gcd = a
lcm = 0 if saved_a == 0 or saved_b == 0 else (saved_a // gcd) * saved_b
return (gcd, lcm)
Worked execution
gcd_lcm(48,18)
L2 gcd_lcm: saved_a, saved_b = abs(a), abs(b) a=48; b=18; saved_a=48; saved_b=18 L5 gcd_lcm: a, b = b, a % b a=18; b=12; saved_a=48; saved_b=18 L5 gcd_lcm: a, b = b, a % b a=12; b=6; saved_a=48; saved_b=18 L5 gcd_lcm: a, b = b, a % b a=6; b=0; saved_a=48; saved_b=18 L6 gcd_lcm: gcd = a a=6; b=0; saved_a=48; saved_b=18; gcd=6 L7 gcd_lcm: lcm = 0 if saved_a == 0 or saved_b == 0 else (saved_a // gcd) * saved_b a=6; b=0; saved_a=48; saved_b=18; gcd=6; lcm=144
Result: (6, 144). Euclid preserves common divisors while shrinking the second operand.
gcd_lcm(-6,8)
L2 gcd_lcm: saved_a, saved_b = abs(a), abs(b) a=-6; b=8; saved_a=6; saved_b=8 L3 gcd_lcm: a, b = saved_a, saved_b a=6; b=8; saved_a=6; saved_b=8 L5 gcd_lcm: a, b = b, a % b a=8; b=6; saved_a=6; saved_b=8 L5 gcd_lcm: a, b = b, a % b a=6; b=2; saved_a=6; saved_b=8 L5 gcd_lcm: a, b = b, a % b a=2; b=0; saved_a=6; saved_b=8 L6 gcd_lcm: gcd = a a=2; b=0; saved_a=6; saved_b=8; gcd=2 L7 gcd_lcm: lcm = 0 if saved_a == 0 or saved_b == 0 else (saved_a // gcd) * saved_b a=2; b=0; saved_a=6; saved_b=8; gcd=2; lcm=24
Result: (2, 24). Results are normalized to nonnegative magnitudes.
Why the solution is correct
The remainder identity preserves exactly the common divisors, while 0<=a%b<b makes the second operand strictly decrease. At b=0, the nonnegative first operand is the GCD. Dividing one original factor by that GCD and multiplying by the other implements the standard GCD-LCM identity without unnecessary intermediate growth.
Time and space
O(log(max(|a|,|b|)+1)) remainder steps and a constant number of integers. Actual arithmetic cost depends on operand bit lengths; division-before-multiplication reduces but does not universally prevent fixed-width overflow.
Common mistakes
Computing a*b//gcd before handling both zeros divides by zero. Returning a negative GCD conflicts with the normalized contract.
Reasoning card
State: The current pair has the same GCD as the original magnitudes. saved_a and saved_b retain those magnitudes for the later LCM calculation.
Invariant: gcd(a,b) is preserved by each transition.
Decision to rehearse: Replace (a,b) with (b,a%b) until b=0.
Finish: Otherwise compute (saved_a//gcd)*saved_b
Transfer exercise
Extend Euclid to return coefficients x,y satisfying a*x+b*y=gcd(a,b).