Loading...
Loading...
Loading...
Two buses leave the depot together. One returns every a minutes and the other every b minutes. Print the GCD (greatest common divisor) of a and b, and the LCM (least common multiple), which is when both buses are next at the depot together.
Use Euclid's method for the GCD: replace (a, b) with (b, a % b) until b is 0. Then LCM = a / GCD × b.
GCD: g and LCM: l.Example
Input
12 18
Output
GCD: 6 LCM: 36
GCD 6. The buses meet after 36 minutes.
Try the problem first. Open one hint at a time.
Keep copies of a and b: the GCD loop changes them.
In the loop, save a % b in a temporary variable, then set a = b and b = the remainder.
Divide before you multiply, and use long, so the LCM does not overflow.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor