Problem Statement
Given two integers, find their least common multiple (LCM). The LCM of two integers is the smallest positive integer that is divisible by both numbers.
Example
-
Input: lcm(4, 6)
Output: 12
-
Input: lcm(7, 3)
Output: 21
-
Input: lcm(10, 15)
Output: 30
Brute Force Approach
Approach
Idea: Start from the larger of the two numbers and iterate upwards to find the smallest number that is divisible by both numbers.
Steps
- Identify the larger of the two numbers as the starting point.
- Iterate upwards, checking if the current number is divisible by both input numbers.
- Return the first number that meets this condition.
Time & Space Complexity
- Time Complexity: O(a * b) in the worst case.
- The maximum possible LCM is
a * b, and we may iterate up to this value.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet
Dry Run
Input: a = 4, b = 6
- Start at the larger number:
6.
- Check divisibility:
6: Not divisible by 4.7: Not divisible by 4 and 6.- ...
12: Divisible by both 4 and 6.
- Return
12.
Efficient Approach Using GCD
Approach
Idea: Use the mathematical relationship between GCD and LCM:
LCM(a, b) = (|a * b|) / GCD(a, b)
The Euclidean Algorithm can efficiently compute the GCD.
Steps
- Compute the GCD of the two numbers using the Euclidean Algorithm.
- Compute the LCM using the formula: LCM(a, b) = (|a * b|) / GCD(a, b).
- Return the LCM.
Time & Space Complexity
- Time Complexity: O(log(min(a, b))) for the GCD computation.
- Space Complexity: O(1)
- Only a few variables are used.
Code Snippet