Problem context and objectives
Mission briefing
Puzzle systems engineer · A game mechanic is behaving incorrectly
Replace a pair with divisor and remainder: The Euclid Engine.
Brute force may pass the demo but fail when the world fills with players.
How you win
- 1Recognize when GCD and LCM matches the clues
- 2Keep this true after every move: every Euclidean pair has the same GCD as the original inputs
- 3Reach the result within O(log min(a,b)) time and O(1) space
Rules and pressure
- Target cost: O(log min(a,b)) time and O(1) space
- State rule: every Euclidean pair has the same GCD as the original inputs
Lesson 1 of 3
Live algorithm trace
GCD and LCM
Complete execution1 of 5
Start from nonnegative magnitudes 48 and 18.
1
x = abs(a); y = abs(b)2
while y is not zero3
x, y = y, x mod y4
gcd = x5
lcm = 0 if either input zero else abs(a/gcd*b)6
return gcd and lcmx = 48y = 18
Truth to preserve / Cost target
Truth to preserve
every Euclidean pair has the same GCD as the original inputs
Cost target
O(log min(a,b)) time and O(1) space
The greatest common divisor is unchanged when (a,b) becomes (b,a mod b). Once the remainder is zero, use gcd times lcm equals the absolute product.
Your call · What should guide every step of this algorithm?