Back to Practice Dashboard
Python BasicsMedium
LCM using Recursion
Learn how to solve the 'LCM using Recursion' problem. This detailed resource details brute force and optimized approaches.
Problem Statement
Medium
Write a function lcm(a, b) that computes the Least Common Multiple (LCM) of two positive integers a and b using recursion. Use the relationship: LCM(a, b) = (a * b) // HCF(a, b). Implement the HCF helper using recursion as well.
Constraints
- •1 <= a, b <= 10^6
Examples
Example 1
Input
a = 4, b = 6
Output
12
Explanation
HCF(4,6) = 2. LCM = (4*6) // 2 = 12. The multiples of 4 are 4,8,12,... and multiples of 6 are 6,12,... The smallest common is 12.
Example 2
Input
a = 12, b = 15
Output
60
Explanation
HCF(12,15) = 3. LCM = (12*15) // 3 = 60.
Example 3
Input
a = 7, b = 3
Output
21
Explanation
HCF(7,3) = 1. LCM = (7*3) // 1 = 21.
Need a Hint?
Use simple arithmetic operators (like modulo `%`, division `//`), conditional checks, or loops to inspect number properties.
Edge Cases to Watch
- Empty list or null input variables
- Single item lists/arrays
- Extremely large input bounds causing integer or stack overflow
Ready to Solve?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.