1843. Shared Factor and Shared Multiple
Two machines repeat on cycles of a and b seconds. The engineer needs the largest block of seconds that divides both cycles evenly, and the first moment they both restart together. These are the greatest common divisor and the least common multiple of a and b.
Return an array of two values: the greatest common divisor first, then the least common multiple. Use the fact that the product of the two numbers equals the product of their gcd and lcm, and find the gcd with Euclid's repeated remainder rule. Divide before you multiply so the intermediate value does not grow too large. Aim for O(log min(a, b)) time.
Example 1
- Input:
- a = 12, b = 18
- Output:
- [6,36]
- Explanation:
The gcd is 6 and the lcm is 12 * 18 / 6 = 36.
Example 2
- Input:
- a = 7, b = 13
- Output:
- [1,91]
- Explanation:
They share no factor, so the lcm is the product, 91.
Example 3
- Input:
- a = 10000000, b = 10000000
- Output:
- [10000000,10000000]
- Explanation:
Equal numbers have gcd and lcm equal to that number.
Constraints
1 ≤ a, b ≤ 107
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(log min(a, b))
- Space
- O(1)