Given two integers N and M, the task is to find their LCM using recursion.
Examples:
Input: N = 2, M = 4
Output: 4
Explanation: LCM of 2, 4 is 4.Input: N = 3, M = 5
Output: 15
Explanation: LCM of 3, 5 is 15.
Approach: The idea is to use the basic elementary method of finding LCM of two numbers. Follow the steps below to solve the problem:
- Define a recursive function LCM() with 3 integer parameters N, M, and K to find LCM of N and M.
- The following base conditions need to be considered:
- If N or M is equal to 1, return N * M.
- If N is equal to M, return N.
- If K < min(N, M):
- If K divides both N and M, return K * LCM(N/K, M/K, 2).
- Otherwise, increment K by 1 and return LCM(N, M, K+1).
- Otherwise, return the product of N and M.
- Finally, print the result of the recursive function as the required LCM.
Below is the implementation of the above approach:
C
// C program for the above approach #include <stdio.h> // Function to return the // minimum of two numbers int Min(int Num1, int Num2) { return Num1 >= Num2 ? Num2 : Num1; } // Utility function to calculate LCM // of two numbers using recursion int LCMUtil(int Num1, int Num2, int K) { // If either of the two numbers // is 1, return their product if (Num1 == 1 || Num2 == 1) return Num1 * Num2; // If both the numbers are equal if (Num1 == Num2) return Num1; // If K is smaller than the // minimum of the two numbers if (K <= Min(Num1, Num2)) { // Checks if both numbers are // divisible by K or not if (Num1 % K == 0 && Num2 % K == 0) { // Recursively call LCM() function return K * LCMUtil( Num1 / K, Num2 / K, 2); } // Otherwise else return LCMUtil(Num1, Num2, K + 1); } // If K exceeds minimum else return Num1 * Num2; } // Function to calculate LCM // of two numbers void LCM(int N, int M) { // Stores LCM of two number int lcm = LCMUtil(N, M, 2); // Print LCM printf("%d", lcm); } // Driver Code int main() { // Given N & M int N = 2, M = 4; // Function Call LCM(N, M); return 0; } |
Output:
4
Time Complexity: O(max(N, M))
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
