Loading...
Loading...
Loading...
Two buses leave the depot together. Bus 1 comes back every a minutes and bus 2 every b minutes. The depot manager wants two numbers: the largest gap that divides both timings (the GCD), and after how many minutes both buses are at the depot together again (the LCM).
Write static long gcd(long a, long b) using Euclid's method and static long lcm(long a, long b) that uses gcd.
Example 1
Input
12 18
Output
6 36
GCD 6; the buses meet again after 36 minutes.
Example 2
Input
4 6
Output
2 12
GCD 2 and LCM 12.
Try the problem first. Open one hint at a time.
Euclid's method: gcd(a, b) = gcd(b, a % b), and gcd(a, 0) = a. A loop or recursion both work.
LCM × GCD = a × b, so LCM = a / gcd × b.
Divide before multiplying to keep the numbers small.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor