Least Common Multiple
This problem was taken from the Coursera Data Structures and Algorithms Specialization, specifically from the Algorithmic Toolbox Course, Week 2, that I’ve recently completed. If you are taking that course or plan to take that course, please don’t look ahead at the solution as it will be against the Honor Code and won’t do you any good.
Problem Introduction
The least common multiple of two positive integers a and b is the least positive integer m that is divisible by both a and b.
Problem Description
Task: Given two integers a and b, find their least common multiple.
Input Format: The two integers a and b are given in the same line separated by space.
Constraints: 1 ≤ a,b ≤ 2 · 10^9
Output Format Output the least common multiple of a and b.
Time Limits: C: 1 sec, C++: 1 sec, Java: 1.5 sec, Python: 5 sec. C#: 1.5 sec, Haskell: 2 sec, JavaScript: 3 sec, Ruby: 3 sec, Scala: 3 sec.
Memory Limit: 512 Mb
Sample 1
Input:
6 8
Output:
24
Sample 2
Input:
28851538 1183019
Output:
1933053046
What To Do
Play with small data sets to find out how the least common multiple LCM(a,b) is related to the greatest common divisor GCD(a,b). Do you see? For any two positive integers a and b, LCM(a,b)·GCD(a,b) = a·b. Prove this property and implement an algorithm for computing the least common multiple using your solution for the greatest common divisor.
My Solution:
Explanation:
This is quite straightforward, nothing too complicated. Here, I’m using this property, GCD (a, b) · LCM (a, b) = a · b, to calculate LCM. I’m using the GCD formula derived in a previous post.
If you can think of any other way to improve this algorithm or if you could point out something that you think I did wrong, you’re more than welcome to reach out to me by responding to this and pointing out the mistakes. If you like this solution, please hit the “Recommend” button below, it’ll mean a lot to me. Thanks.
