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
Dry Run
Input: a = 4, b = 6
- Compute GCD:
4 % 6 = 4, update a = 6, b = 4.6 % 4 = 2, update a = 4, b = 2.4 % 2 = 0, update a = 2, b = 0.- GCD is
2.
- Compute LCM:
[ ext{LCM} = rac{|4 \cdot 6|}{2} = 12 ]
- Return
12.
Complexity Analysis
| Operation | Brute Force | Efficient Using GCD |
|---|
| Time Complexity | O(a * b) | O(log(min(a, b))) |
| Space Complexity | O(1) | O(1) |
Conclusion
- The brute force approach is simple but inefficient for large numbers due to its O(a * b) time complexity.
- The GCD-based approach optimizes the process to O(log(min(a, b))) time complexity using the Euclidean Algorithm.
- Understanding the relationship between GCD and LCM helps in deriving efficient solutions.