Problem Statement

You are given two integers n1 and n2. You need find the Lowest Common Multiple (LCM) of the two given numbers. Return the LCM of the two numbers.

The Lowest Common Multiple (LCM) of two integers is the lowest positive integer that is divisible by both the integers.

Examples

Example 1:

Input: n1 = 4, n2 = 6
Output: 12

Explanation: 4*3 = 12, 6*2 = 12
12 is the lowest integer that is divisible by both 4 and 6.

Example 2:

Input: n1 = 3, n2 = 5
Output: 15

Explanation: 3*5 = 15, 5*3 = 15
15 is the lowest integer that is divisible by both 3 and 5.

Approaches

1️⃣ Brute Force Approach

Intuition:

In a naive approach to finding the LCM of two given numbers, the multiples of the larger number (considering multiples of the larger number instead of the smaller number will trim unfruitful iterations) can be checked if it is common for both numbers. Any such multiple found will be common to both the given numbers, and that will be the required LCM.

Approach:

1. Initialize a variable lcm to store the LCM of given numbers.
2. Run a loop finding all the multiples of greater number and in every pass, check if the multiple is common for both numbers. If found common, store the multiple as lcm and terminate the loop.
3. The LCM for the two numbers will be stored in variable lcm.

Dry Run:

Initialization:

N1 = 6
N2 = 4

n = max(N1, N2)
	max(6, 4) = 6

First Iteration:

i = 1

mul = n*i
	n * 1 = 6*1 = 6

mul % N1 == 0 && mul % N2 == 0
6 % 6 == 0 && 6 % 4 == 0
0 == 0 && 2 == 0
false

Second Iteration:

i = 2

mul = n*i
	n * 2 = 6*2 = 12

mul % N1 == 0 && mul % N2 == 0
12 % 6 == 0 && 12 % 4 == 0
0 == 0 && 0 == 0
true

mul = 12
return mul

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to find LCM of n1 and n2
    int LCM(int n1,int n2) {
        //Variable to store lcm
        int lcm;
        
        // Variable to store max of n1 & n2
        int n = max(n1, n2);
        int i = 1;
        
        while(1) {
            // Variable to store multiple
            int mul = n * i;
            
            /* Checking if multiple is common
            common for both n1 and n2 */
            if(mul % n1 == 0 && mul % n2 == 0) {
                lcm = mul;
                break;
            }
            i++;
        }
        
        // Return the stored LCM
        return lcm;
    }
};

int main()
{
    int n1 = 4, n2 = 12;
    
    /* Creating and instance of 
    Solution class */
    Solution sol; 
    
    // Function call to get LCM of n1 and n2
    int ans = sol.LCM(n1, n2);
    cout << "The LCM of" << n1 << " and " << n2 << " is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(min(N1, N2)) – In the worst-case scenario, when n1 and n2 are coprime, the loop runs for O(n1 * n2 / max(n1, n2)) iterations which is equivalent to O(min(n1, n2)).
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.

2️⃣ Optimal Approach (using HCF | GCF)

Intuition:

The optimal way to find LCM to two numbers is by finding their GCD and using the formula:

lcm(n1, n2) = (n1 * n2) / gcd(n1, n2).

Approach:

1. Find the GCD of two numbers and store it in some variable.
2. The LCM for the two numbers can be found directly using the formula mentioned above.

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to find the
    GCD of two numbers*/
    int GCD(int n1, int n2) {
        
        /* Continue loop as long as both 
         n1 and n2 are greater than zero */
        while(n1 > 0 && n2 > 0) {
            
            /* If n1 is greater than n2, perform
             modulo operation - n1 % n2 */
            if(n1 > n2) {
                n1 = n1 % n2;
            }
            
            /* Else perform modulo
            operation - n2 % n1 */
            else {
                n2 = n2 % n1;
            }
        }
        
        // If n1 is zero, GCD is stored in n2
        if(n1 == 0) return n2;
        
        //else GCD is stored in n1
        return n1;
    }
    
public:
    // Function to find LCM of n1 and n2
    int LCM(int n1,int n2) {
        //Function call to find gcd
        int gcd = GCD(n1, n2);
        
        int lcm = (n1 * n2) / gcd;
        
        // Return the LCM
        return lcm;
    }
};

int main()
{
    int n1 = 3, n2 = 5;
    
    /* Creating and instance of 
    Solution class */
    Solution sol; 
    
    // Function call to get LCM of n1 and n2
    int ans = sol.LCM(n1, n2);
    cout << "The LCM of" << n1 << " and " << n2 << " is: " << ans;
    
    return 0;
}

Complexity Analysis:

• Time Complexity:O(log(min(N1, N2))) – Finding GCD of two numbers, along with some constant time operations.
• Space Complexity:O(1) – Using a couple of variables i.e., constant space.