LCM of two numbers

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:

Initialize a variable lcm to store the LCM of given numbers.
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.
The LCM for the two numbers will be stored in variable lcm.

Dry Run:

Solution:

#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;
}
class Solution {
    // Function to find LCM of n1 and n2
    public int LCM(int n1, int n2) {
        // Variable to store lcm
        int lcm;
        
        // Variable to store max of n1 & n2
        int n = Math.max(n1, n2);
        int i = 1;
        
        while (true) {
            // 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;
    }

    public static void main(String[] args) {
        int n1 = 4, n2 = 12;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        // Function call to get LCM of n1 and n2
        int ans = sol.LCM(n1, n2);
        System.out.println("The LCM of " + n1 + " and " + n2 + " is: " + ans);
    }
}
class Solution:
    # Function to find LCM of n1 and n2
    def LCM(self, n1, n2):
        # Variable to store lcm
        lcm = 0
        
        # Variable to store max of n1 & n2
        n = max(n1, n2)
        i = 1
        
        while True:
            # Variable to store multiple
            mul = n * i
            
            # Checking if multiple is common
            # common for both n1 and n2
            if mul % n1 == 0 and mul % n2 == 0:
                lcm = mul
                break
            i += 1
        
        # Return the stored LCM
        return lcm

# Input values
n1 = 4
n2 = 12

# Creating an instance of Solution class
sol = Solution()

# Function call to get LCM of n1 and n2
ans = sol.LCM(n1, n2)
print("The LCM of", n1, "and", n2, "is:", ans)
class Solution {
    // Function to find LCM of n1 and n2
    LCM(n1, n2) {
        // Variable to store lcm
        let lcm;
        
        // Variable to store max of n1 & n2
        let n = Math.max(n1, n2);
        let i = 1;
        
        while (true) {
            // Variable to store multiple
            let 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;
    }
}

// Input values
let n1 = 4;
let n2 = 12;

/* Creating an instance of 
Solution class */
let sol = new Solution();

// Function call to get LCM of n1 and n2
let ans = sol.LCM(n1, n2);
console.log("The LCM of " + n1 + " and " + n2 + " is: " + ans);

Complexity Analysis:

Time Complexity: O(min(N₁, N₂)) – 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.

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:

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

Dry Run:

Solution:

#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;
}
class Solution {
    // Function to find the GCD of two numbers
    private 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;
    }
    
    // Function to find LCM of n1 and n2
    public 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;
    }

    public static void main(String[] args) {
        int n1 = 3, n2 = 5;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution();
        
        // Function call to get LCM of n1 and n2
        int ans = sol.LCM(n1, n2);
        System.out.println("The LCM of " + n1 + " and " + n2 + " is: " + ans);
    }
}
class Solution:
    # Function to find the GCD of two numbers
    def GCD(self, n1, n2):
        
        # Continue loop as long as both 
        # n1 and n2 are greater than zero
        while n1 > 0 and 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
    
    # Function to find LCM of n1 and n2
    def LCM(self, n1, n2):
        # Function call to find gcd
        gcd = self.GCD(n1, n2)
        
        lcm = (n1 * n2) // gcd
        
        # Return the LCM
        return lcm

# Input numbers
n1, n2 = 3, 5

# Creating an instance of Solution class
sol = Solution()

# Function call to get LCM of n1 and n2
ans = sol.LCM(n1, n2)
print(f"The LCM of {n1} and {n2} is: {ans}")
class Solution {
    // Function to find the GCD of two numbers
    GCD(n1, 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;
    }
    
    // Function to find LCM of n1 and n2
    LCM(n1, n2) {
        // Function call to find gcd
        let gcd = this.GCD(n1, n2);
        
        let lcm = (n1 * n2) / gcd;
        
        // Return the LCM
        return lcm;
    }
}

// Input numbers
let n1 = 3, n2 = 5;

// Creating an instance of Solution class
let sol = new Solution();

// Function call to get LCM of n1 and n2
let ans = sol.LCM(n1, n2);
console.log(`The LCM of ${n1} and ${n2} is: ${ans}`);

Complexity Analysis:

Time Complexity: O(log(min(N₁, N₂))) – Finding GCD of two numbers, along with some constant time opeations

Space Complexity: O(1) – Using a couple of variables i.e., constant space.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Notes

Code