Skip to main content

Math Basics

Calculate the LCM and GCD of two numbers Solution In C++/Java/Python/JS

Problem Description:

Given two integers A and B, find their Greatest Common Divisor (GCD) and Least Common Multiple (LCM).
The GCD (Greatest Common Divisor) of two numbers is the largest number that divides both A and B without leaving a remainder.
The LCM (Least Common Multiple) of two numbers is the smallest positive number that is a multiple of both A and B.
calculate-the-lcm-and-gcd-of-two-numbers-problem-description
calculate-the-lcm-and-gcd-of-two-numbers-problem-description

Examples:

Input: A = 8, B = 14
Output: GCD = 2, LCM = 56
Explanation:
Factors of 8: {1, 2, 4, 8}
Factors of 14: {1, 2, 7, 14}
GCD(8, 14) = 2 (largest common factor)
LCM(8, 14) = (8 × 14) / 2 = 56

Input: A = 12, B = 18
Output: GCD = 6, LCM = 36
Explanation:
Factors of 12: {1, 2, 3, 4, 6, 12}
Factors of 18: {1, 2, 3, 6, 9, 18}
GCD(12, 18) = 6 (largest common factor)
LCM(12, 18) = (12 × 18) / 6 = 36

Understanding GCD and LCM

What is GCD (Greatest Common Divisor)?

The GCD of two numbers is the largest number that divides both numbers without leaving a remainder. It represents the highest common factor shared by the numbers.

In simple terms, it's the biggest number that both numbers share as a factor.

For example, let's take 12 and 18.

  • The factors of 12 are: 1, 2, 3, 4, 6, 12
  • The factors of 18 are: 1, 2, 3, 6, 9, 18
  • The common factors between them are 1, 2, 3, and 6, but the largest one is 6.
  • So, the GCD of 12 and 18 is 6.

Another example:
Consider 8 and 14.

  • Factors of 8: 1, 2, 4, 8
  • Factors of 14: 1, 2, 7, 14
  • The common factor is 1 and 2, and the largest is 2.
  • So, the GCD of 8 and 14 is 2.

GCD is useful in many situations, such as simplifying fractions. If you have 12/18, you can divide both 12 and 18 by their GCD (6) to simplify it to 2/3.

What is LCM (Least Common Multiple)?

The LCM of two numbers is the smallest positive number that is a multiple of both numbers. It represents the first number that both given numbers can divide evenly.

In other words, it’s the first number that both numbers can divide into evenly without leaving a remainder.

Let’s take an example with 4 and 6.

  • The multiples of 4 are: 4, 8, 12, 16, 20, 24, ...
  • The multiples of 6 are: 6, 12, 18, 24, 30, ...
  • The common multiples are 12, 24, ..., but the smallest one is 12.
  • So, the LCM of 4 and 6 is 12.

Another example:
Consider 5 and 7.

  • The multiples of 5 are: 5, 10, 15, 20, 25, 30, 35, ...
  • The multiples of 7 are: 7, 14, 21, 28, 35, 42, ...
  • The smallest common multiple is 35.
  • So, the LCM of 5 and 7 is 35.

LCM is useful in real life when dealing with things like scheduling or finding a common denominator in fractions. For example, if one bus arrives every 4 minutes and another every 6 minutes, they will both arrive together every 12 minutes—which is the LCM of 4 and 6.

Brute Force Approach

Now that we understand what GCD (Greatest Common Divisor) and LCM (Least Common Multiple) mean, let's see how we can calculate them using the brute force method. This method is simple to understand but can be slow for large numbers.

Brute Force Method to Find GCD

The GCD of two numbers is the largest number that divides both numbers exactly.

Now, let’s go through the process of finding the Greatest Common Divisor (GCD) of two numbers step by step, using a systematic approach. We will take the numbers 12 and 18 as an example.

The GCD of two numbers is always less than or equal to the smaller number.

  • Here, we have A = 12 and B = 18.
  • The smaller number is 12.

Since GCD is the largest number that divides both A and B, we start checking from 12 downward and look for the largest number that divides both without a remainder.

Example:

We start from 12 and go down one number at a time until we find the largest divisor of both numbers.

  1. Check if 12 divides both 12 and 18
  • 12 % 12 = 0 (12 is divisible by 12)
  • 18 % 12 = 6 (12 does not divide 18 completely)
  • So, 12 is NOT the GCD
  1. Check if 11 divides both 12 and 18
  • 12 % 11 = 1
  • 18 % 11 = 7
  • 11 is NOT the GCD
  1. Check if 10 divides both 12 and 18
  • 12 % 10 = 2
  • 18 % 10 = 8
  • 10 is NOT the GCD
  1. Check if 9 divides both 12 and 18
  • 12 % 9 = 3
  • 18 % 9 = 0
  • 9 is NOT the GCD (it doesn’t divide 12)
  1. Check if 8 divides both 12 and 18
  • 12 % 8 = 4
  • 18 % 8 = 2
  • 8 is NOT the GCD
  1. Check if 7 divides both 12 and 18
  • 12 % 7 = 5
  • 18 % 7 = 4
  • 7 is NOT the GCD
  1. Check if 6 divides both 12 and 18
  • 12 % 6 = 0 (6 divides 12 completely)
  • 18 % 6 = 0 (6 divides 18 completely)
  • 6 is the largest number that divides both 12 and 18
  • So, GCD(12, 18) = 6

To sum up:

  • Start from the smaller of the two numbers.
  • Check if this number divides both numbers completely (i.e., remainder is 0).
  • If it does, this is the GCD. Otherwise, decrease the number and check again.
  • Stop when we find the largest number that divides both.
FUNCTION findGCD(A, B):

    // Start from the smaller number
    minNum = MIN(A, B)  
    
    FOR i FROM minNum TO 1 STEP -1:

        // Check if i divides both numbers
        IF (A MOD i == 0 AND B MOD i == 0):  

            // i is the GCD
            RETURN i  
    END FOR

Brute Force Method to Find LCM

The LCM of two numbers is the smallest number that is a multiple of both.

Now, let’s go through the process of finding the Least Common Multiple (LCM) of two numbers step by step, using a systematic approach. We will take the numbers 4 and 6 as an example.

The LCM of two numbers is always greater than or equal to the larger number.

  • Here, we have A = 4 and B = 6.
  • The larger number is 6.

Since LCM is the smallest number that is a multiple of both A and B, we start checking from 6 upward and look for the first number that both 4 and 6 can divide evenly.

Example:

We start from 6 and keep increasing by 1 until we find a multiple of both numbers.

  1. Check if 6 is divisible by both 4 and 6
  • 6 % 4 = 2 (6 is NOT divisible by 4)
  • 6 % 6 = 0 (6 is divisible by 6)
  • So, 6 is NOT the LCM
  1. Check if 7 is divisible by both 4 and 6
  • 7 % 4 = 3
  • 7 % 6 = 1
  • 7 is NOT the LCM
  1. Check if 8 is divisible by both 4 and 6
  • 8 % 4 = 0
  • 8 % 6 = 2
  • 8 is NOT the LCM
  1. Check if 9 is divisible by both 4 and 6
  • 9 % 4 = 1
  • 9 % 6 = 3
  • 9 is NOT the LCM
  1. Check if 10 is divisible by both 4 and 6
  • 10 % 4 = 2
  • 10 % 6 = 4
  • 10 is NOT the LCM
  1. Check if 11 is divisible by both 4 and 6
  • 11 % 4 = 3
  • 11 % 6 = 5
  • 11 is NOT the LCM
  1. Check if 12 is divisible by both 4 and 6
  • 12 % 4 = 0 (12 is divisible by 4)
  • 12 % 6 = 0 (12 is divisible by 6)
  • Since 12 is the first number that both 4 and 6 divide evenly, it is the LCM!

So, LCM(4, 6) = 12

To sum up:

  1. Start from the maximum of the two numbers.
  2. Keep increasing this number until we find a multiple of both A and B.
  3. The first number that satisfies this condition is the LCM.
FUNCTION findLCM(A, B):

    // Start from the larger number
    maxNum = MAX(A, B)  

    // Infinite loop until we find the LCM
    WHILE TRUE:  

        // Check divisibility
        IF (maxNum MOD A == 0 AND maxNum MOD B == 0):  

            // Found LCM
            RETURN maxNum 

        // Try next number
        INCREMENT maxNum  
    END WHILE

Calculate the LCM and GCD of two numbers Solution

Code Implementation
1. Calculate the LCM and GCD of two numbers Solution C++ Try on Compiler 
#include <iostream>
using namespace std;

// Function to calculate GCD using brute force method
int findGCD(int a, int b) {

    // Start from the smaller number
    int minNum = min(a, b); 
    for (int i = minNum; i >= 1; i--) {

        // Check if i divides both
        if (a % i == 0 && b % i == 0) { 

            // Largest common divisor found
            return i;  
        }
    }

    // If no other divisor is found, GCD is 1
    return 1; 
}

// Function to calculate LCM using brute force method
int findLCM(int a, int b) {

    // Start from the larger number
    int maxNum = max(a, b); 
    while (true) {

        // Check if maxNum is a multiple of both
        if (maxNum % a == 0 && maxNum % b == 0) { 

            // Smallest common multiple found
            return maxNum; 
        }

        // Try next number
        maxNum++; 
    }
}

// Main function
int main() {
    int num1, num2;
    
    // Input two numbers
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;

    // Calculate GCD and LCM using brute force
    int gcd = findGCD(num1, num2);
    int lcm = findLCM(num1, num2);

    // Output results
    cout << "GCD of " << num1 << " and " << num2 << " is: " << gcd << endl;
    cout << "LCM of " << num1 << " and " << num2 << " is: " << lcm << endl;

    return 0;
}

2. Calculate the LCM and GCD of two numbers Solution Java Try on Compiler 
import java.util.Scanner;

public class GCD_LCM_BruteForce {
    // Function to calculate GCD using brute force method
    public static int findGCD(int a, int b) {

        // Start from the smaller number
        int minNum = Math.min(a, b); 
        for (int i = minNum; i >= 1; i--) {

            // Check if i divides both
            if (a % i == 0 && b % i == 0) { 

                // Largest common divisor found
                return i;  
            }
        }

        // If no other divisor is found, GCD is 1
        return 1; 
    }

    // Function to calculate LCM using brute force method
    public static int findLCM(int a, int b) {

        // Start from the larger number
        int maxNum = Math.max(a, b); 
        while (true) {

            // Check if maxNum is a multiple of both
            if (maxNum % a == 0 && maxNum % b == 0) { 

                // Smallest common multiple found
                return maxNum; 
            }

            // Try next number
            maxNum++; 
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        // Input two numbers
        System.out.print("Enter two numbers: ");
        int num1 = sc.nextInt();
        int num2 = sc.nextInt();
        sc.close();

        // Calculate GCD and LCM using brute force
        int gcd = findGCD(num1, num2);
        int lcm = findLCM(num1, num2);

        // Output results
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd);
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm);
    }
}

3. Calculate the LCM and GCD of two numbers Solution Python Try on Compiler 
def findGCD(a, b):
    """Function to calculate GCD using brute force method"""

    # Start from the smaller number
    min_num = min(a, b)  

    # Check from min_num down to 1
    for i in range(min_num, 0, -1):  

        # Check if i divides both
        if a % i == 0 and b % i == 0:  

            # Largest common divisor found
            return i  

    # If no other divisor is found, GCD is 1
    return 1  

def findLCM(a, b):
    """Function to calculate LCM using brute force method"""

    # Start from the larger number
    max_num = max(a, b)  
    while True:

        # Check if max_num is a multiple of both
        if max_num % a == 0 and max_num % b == 0:  

            # Smallest common multiple found
            return max_num  

        # Try next number
        max_num += 1  

# Input two numbers
num1, num2 = map(int, input("Enter two numbers: ").split())

# Calculate GCD and LCM using brute force
gcd = findGCD(num1, num2)
lcm = findLCM(num1, num2)

# Output results
print(f"GCD of {num1} and {num2} is: {gcd}")
print(f"LCM of {num1} and {num2} is: {lcm}")

4. Calculate the LCM and GCD of two numbers Solution Javascript Try on Compiler 
// Function to calculate GCD using brute force method
function findGCD(a, b) {

    // Start from the smaller number
    let minNum = Math.min(a, b); 
    for (let i = minNum; i >= 1; i--) {

        // Check if i divides both
        if (a % i === 0 && b % i === 0) { 

            // Largest common divisor found
            return i;  
        }
    }

    // If no other divisor is found, GCD is 1
    return 1; 
}

// Function to calculate LCM using brute force method
function findLCM(a, b) {

    // Start from the larger number
    let maxNum = Math.max(a, b); 
    while (true) {

        // Check if maxNum is a multiple of both
        if (maxNum % a === 0 && maxNum % b === 0) { 

            // Smallest common multiple found
            return maxNum; 
        }

        // Try next number
        maxNum++; 
    }
}

// Take input from the user
const num1 = parseInt(prompt("Enter first number:"));
const num2 = parseInt(prompt("Enter second number:"));

// Calculate GCD and LCM using brute force
const gcd = findGCD(num1, num2);
const lcm = findLCM(num1, num2);

// Output results
console.log(`GCD of ${num1} and ${num2} is: ${gcd}`);
console.log(`LCM of ${num1} and ${num2} is: ${lcm}`);

Complexity Analysis for Calculate the LCM and GCD of two numbers Solution

Time Complexity: O(a × b)

1. Brute Force GCD Time Complexity Analysis

  • Start from min(a, b) and decrement down to 1.
  • The first number that divides both is the GCD.
  • In the worst case, this loop runs O(min(a, b)) times.

Time Complexity: O(min(a, b))

2. Brute Force LCM Time Complexity Analysis

  • Start from max(a, b), and keep incrementing until a number is divisible by both a and b.
  • The worst case happens when LCM(a, b) = a × b (when a and b are coprime).
  • In the worst case, this loop runs up to O(a × b) times.

Time Complexity: O(a × b)

Space Complexity: O(1)

Auxiliary Space Complexity: O(1 )
Explanation: We are only using a few integer variables—such as minNum (for GCD) and maxNum (for LCM)—to track calculations. No additional data structures like arrays, lists, or hash maps are used.
Thus, the auxiliary space complexity is O(1) since only a constant amount of extra space is required.

Total Space Complexity: O(1)
Explanation: Unlike problems involving arrays or lists, our algorithm only takes two integer inputs (a and b). Since we do not use any additional data structures, the total space used remains constant.
Thus, the total space complexity is O(1).

Can we optimize it?

Now, let's explore whether we can develop a more optimized solution to further improve efficiency.

Calculate the LCM and GCD of two numbers Algorithm

Now that we understand the brute force method for finding the Greatest Common Divisor (GCD), let’s explore a more optimized approach: the Euclidean Algorithm. This method significantly improves efficiency compared to checking divisibility for all numbers.

Euclidean Algorithm Using Subtraction

The fundamental idea behind this algorithm is that the GCD of two numbers remains the same if we subtract the smaller number from the larger one.

Let’s understand why with a simple example:

Example 1: Finding GCD(48, 18) using subtraction

  1. We know that GCD(48, 18) = x (some number x that divides both 48 and 18).
  2. If x is a divisor of both 48 and 18, it must also be a divisor of (48 - 18).
  3. That means:
    • GCD(48, 18) = GCD(30, 18) (since x must divide both).
  4. Now, applying the same logic again:
    • GCD(30, 18) = GCD(12, 18)
    • GCD(12, 18) = GCD(6, 12)
    • GCD(6, 12) = GCD(6, 6)
    • Now, both numbers are the same, so GCD = 6.

Why does this work?

  • If a number x divides both 48 and 18, then x must also divide their difference (48 - 18 = 30).
  • This logic applies repeatedly, reducing the numbers until they are equal, which is the GCD.
We are continuously reducing the problem without changing the actual GCD.

Calculate the GCD of two numbers Examples

Example 1: Finding GCD of 48 and 18

Let's apply this step-by-step:

  1. 48 - 18 = 30 (Now, we find GCD of 30 and 18)
  2. 30 - 18 = 12 (Now, we find GCD of 12 and 18)
  3. 18 - 12 = 6 (Now, we find GCD of 6 and 12)
  4. 12 - 6 = 6 (Now, we find GCD of 6 and 6)
  5. Since both numbers are now the same (6), we stop.

Final Answer: GCD(48, 18) = 6

Example 2: Finding GCD of 35 and 10

  1. 35 - 10 = 25
  2. 25 - 10 = 15
  3. 15 - 10 = 5
  4. 10 - 5 = 5
  5. Since both numbers are now 5, we stop.

Final Answer: GCD(35, 10) = 5

Calculate the GCD of two numbers Algorithm

function gcd(a, b):

    // Repeat until both numbers become the same
    while a ≠ b:  
        if a > b:

            // Subtract smaller number from larger
            a = a - b  
        else:

            // Subtract smaller number from larger
            b = b - a  

    // or return b (both are the same at this point)
    return a

Optimized Euclidean Algorithm Using Division (Modulo Operator)

Instead of repeatedly subtracting the smaller number, we use division to reduce the larger number much faster.

We noticed in the subtraction method that we keep subtracting b from a multiple times.

What if instead of subtracting multiple times, we directly find how much is left after division?
This is exactly what modulo (%) does—it finds the remainder after division in one step instead of subtracting repeatedly.

Instead of subtracting b from a repeatedly, we can directly compute:

a % b → the remainder when a is divided by b

This tells us the "leftover" part after division, eliminating the need for multiple subtractions.

Let's compare the subtraction method and the modulo method side by side:

Subtraction Method (GCD of 48 and 18):

  1. 48 - 18 = 30
  2. 30 - 18 = 12
  3. 18 - 12 = 6
  4. 12 - 6 = 6
  5. GCD = 6

Modulo Method (GCD of 48 and 18 using % operator):

  1. 48 % 18 = 12 (because 48 divided by 18 gives remainder 12)
  2. 18 % 12 = 6
  3. 12 % 6 = 0
  4. GCD = 6 (last non-zero remainder)

What changed?

  • Instead of subtracting multiple times, we directly calculate the remainder using a % b.
  • This makes the process faster and more efficient.
Final Transition Formula: GCD(a, b) = GCD(b, a % b)

This formula is the optimized version of the subtraction-based Euclidean Algorithm.

Understand with an example:

Calculate gcd(48, 18)
Step 1: 48 % 18 = 12 → gcd(18, 12)
Step 2: 18 % 12 = 6 → gcd(12, 6)
Step 3: 12 % 6 = 0 → gcd(6, 0)
Step 4: Base case reached, return 6

function gcd(a, b):
    if b == 0:

        // Base case: If remainder is 0, return a
        return a  

    // Recursively call with (b, remainder of a % b)
    return gcd(b, a % b)

Use the modulo-based Euclidean algorithm because it reduces the number much faster and works efficiently for large numbers.

Finding LCM Using GCD

Now that we've understood how GCD can be efficiently computed using the Euclidean algorithm, let's move on to LCM (Least Common Multiple) and see how GCD can help us find it more efficiently.

From number theory, there's an important relationship between LCM and GCD:

LCM(a,b) = |a×b| / GCD(a,b)

Why Does This Work?

  • LCM is a multiple of both numbers.
  • GCD is the greatest number that divides both numbers.
  • Multiplying a and b gives a number that includes all factors of both.
  • Dividing by GCD removes the extra factors, leaving the smallest common multiple.

Let’s break it down with an example:

Example: Finding LCM(12, 18) using GCD

  1. Find GCD(12, 18) using the Euclidean algorithm:
    • GCD(12, 18) = 6
  2. Apply the formula: LCM(12,18) = 12 × 18 / 6 = 216 / 6 = 36
  3. LCM = 36 (which is correct)

Instead of checking each multiple manually, we used GCD to simplify the calculation, making it much faster.

Calculate the LCM of two numbers Examples

Example Calculation: LCM(15, 20)

  1. Compute GCD(15, 20):
    • 20 % 15 = 5 → gcd(15, 5)
    • 15 % 5 = 0 → gcd = 5
  3. Apply the formula:LCM(15,20) = 15×20/5 = 300/ 5 = 60
  4. LCM(15,20) = 60

Calculate the LCM of two numbers Algorithm

function gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

function lcm(a, b):
    return (a * b) / gcd(a, b)

Calculate the LCM and GCD of two numbers Solution

Code Implementation
1. Calculate the LCM and GCD of two numbers Solution C++ Try on Compiler 
#include <iostream>
using namespace std;

// Function to compute GCD using Recursive Euclidean Algorithm (Modulo method)
int findGCD(int a, int b) {
    if (b == 0)  

        // Base case: If remainder is 0, return a
        return a;  

    // Recursively call with (b, remainder of a % b)
    return findGCD(b, a % b);  
}

// Function to compute LCM using the formula: LCM(a, b) = (a * b) / GCD(a, b)
int findLCM(int a, int b) {

    // Avoids overflow by dividing first
    return (a / findGCD(a, b)) * b;  
}

// Main function
int main() {
    int num1, num2;
    
    // Input two numbers
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;

    // Compute GCD and LCM
    int gcd = findGCD(num1, num2);
    int lcm = findLCM(num1, num2);

    // Output results
    cout << "GCD of " << num1 << " and " << num2 << " is: " << gcd << endl;
    cout << "LCM of " << num1 << " and " << num2 << " is: " << lcm << endl;

    return 0;
}

2. Calculate the LCM and GCD of two numbers Solution Java Try on Compiler 
import java.util.Scanner;

public class GCD_LCM {
    
    // Function to compute GCD using Recursive Euclidean Algorithm (Modulo method)
    public static int findGCD(int a, int b) {
        if (b == 0)  

            // Base case: If remainder is 0, return a
            return a;  

        // Recursively call with (b, remainder of a % b)
        return findGCD(b, a % b);  
    }

    // Function to compute LCM using the formula: LCM(a, b) = (a * b) / GCD(a, b)
    public static int findLCM(int a, int b) {

        // Avoids overflow by dividing first
        return (a / findGCD(a, b)) * b;  
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Input two numbers
        System.out.print("Enter two numbers: ");
        int num1 = scanner.nextInt();
        int num2 = scanner.nextInt();
        
        // Compute GCD and LCM
        int gcd = findGCD(num1, num2);
        int lcm = findLCM(num1, num2);

        // Output results
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd);
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm);

        scanner.close();
    }
}

3. Calculate the LCM and GCD of two numbers Solution Python Try on Compiler 
# Function to compute GCD using Recursive Euclidean Algorithm (Modulo method)
def findGCD(a, b):
    if b == 0:

        # Base case: If remainder is 0, return a
        return a  

    # Recursively call with (b, remainder of a % b)
    return findGCD(b, a % b)  

# Function to compute LCM using the formula: LCM(a, b) = (a * b) / GCD(a, b)
def findLCM(a, b):

    # Avoids overflow by dividing first
    return (a // findGCD(a, b)) * b  

# Main function
if __name__ == "__main__":
    # Input two numbers
    num1, num2 = map(int, input("Enter two numbers: ").split())

    # Compute GCD and LCM
    gcd = findGCD(num1, num2)
    lcm = findLCM(num1, num2)

    # Output results
    print(f"GCD of {num1} and {num2} is: {gcd}")
    print(f"LCM of {num1} and {num2} is: {lcm}")

4. Calculate the LCM and GCD of two numbers Solution Javascript Try on Compiler 
// Function to compute GCD using Recursive Euclidean Algorithm (Modulo method)
function findGCD(a, b) {
    if (b === 0)  

        // Base case: If remainder is 0, return a
        return a;  

     // Recursively call with (b, remainder of a % b)
    return findGCD(b, a % b); 
}

// Function to compute LCM using the formula: LCM(a, b) = (a * b) / GCD(a, b)
function findLCM(a, b) {

    // Avoids overflow by dividing first
    return (a / findGCD(a, b)) * b;  
}

// Main function to take input and compute results
const readline = require('readline').createInterface({
    input: process.stdin,
    output: process.stdout
});

readline.question("Enter two numbers: ", input => {
    let [num1, num2] = input.split(" ").map(Number);

    // Compute GCD and LCM
    let gcd = findGCD(num1, num2);
    let lcm = findLCM(num1, num2);

    // Output results
    console.log(`GCD of ${num1} and ${num2} is: ${gcd}`);
    console.log(`LCM of ${num1} and ${num2} is: ${lcm}`);

    readline.close();
});

Complexity Analysis for Calculate the LCM and GCD of two numbers Solution

Time Complexity: O(log(min(a, b)))

The time complexity of the GCD function using the Euclidean Algorithm (modulo method) is O(log(min(a, b))). This is because, in each recursive step, the problem size is significantly reduced by replacing (a, b) with (b, a % b), which effectively halves the value of one of the numbers in many cases. This follows a pattern similar to the Fibonacci sequence, leading to logarithmic complexity.

For the LCM function, we use the formula LCM(a, b) = (a / GCD(a, b)) * b. The time complexity of computing LCM is also O(log(min(a, b))), as it relies on the GCD calculation, and the multiplication and division operations take constant time O(1).

Thus, the overall time complexity for computing both GCD and LCM is O(log(min(a, b))), making this approach extremely efficient, even for large numbers

Space Complexity: O(log(min(a, b)))

Auxiliary Space Complexity: O(log(min(a, b)))
Explanation: The space complexity of the GCD function is O(log(min(a, b))) due to recursive calls using the call stack. Each recursive step reduces the problem size significantly, leading to a logarithmic depth of recursion. The LCM function itself operates in O(1) space, as it only performs arithmetic operations and does not use any additional data structures.

Total Space Complexity: O(log(min(a, b)))
Explanation: Since no additional data structures are allocated beyond function call stack space, the total space complexity of the algorithm remains O(log(min(a, b))). However, if the recursive GCD function is converted to an iterative approach, the auxiliary space can be further optimized to O(1).

Built-in GCD Functions

Most programming languages provide built-in functions to compute the Greatest Common Divisor (GCD) efficiently using optimized versions of the Euclidean Algorithm. These functions eliminate the need for writing custom implementations and are highly optimized for performance.

Built-in GCD Functions in Different Languages

  1. C++ (STL)
    In C++, the Standard Library (<numeric>) provides the std::gcd() function:
#include <iostream>
#include <numeric> // For std::gcd
using namespace std;

int main() {
    int a = 12, b = 18;
    cout << "GCD: " << gcd(a, b) << endl; // Output: 6
    return 0;
}
  1. Python (math module)
    Python has a built-in math.gcd() function:
import math
a, b = 12, 18
print("GCD:", math.gcd(a, b))  # Output: 6
  1. Java (BigInteger Class)
    Java provides a built-in gcd() function under the BigInteger class:
import java.math.BigInteger;

public class Main {
    public static void main(String[] args) {
        int a = 12, b = 18;
        System.out.println("GCD: " + BigInteger.valueOf(a).gcd(BigInteger.valueOf(b)));
    }
}
  1. JavaScript (Custom Implementation Needed)
    JavaScript does not have a built-in gcd() function. Since JavaScript lacks a built-in function, we use the recursive Euclidean method.

Calculate the LCM and GCD of two numbers Solution

Code Implementation
1. Calculate the LCM and GCD of two numbers Solution C++ Try on Compiler 
#include <iostream>
#include <numeric> // For std::gcd
using namespace std;

int main() {
    int num1, num2;

    // Input two numbers
    cout << "Enter two numbers: ";
    cin >> num1 >> num2;

    // Compute GCD using built-in function
    int gcd = gcd(num1, num2);

    // Compute LCM using formula: LCM(a, b) = (a / GCD(a, b)) * b
    int lcm = (num1 / gcd) * num2; 

    // Output results
    cout << "GCD of " << num1 << " and " << num2 << " is: " << gcd << endl;
    cout << "LCM of " << num1 << " and " << num2 << " is: " << lcm << endl;

    return 0;
}

2. Calculate the LCM and GCD of two numbers Solution Java Try on Compiler 
import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Input two numbers
        System.out.print("Enter two numbers: ");
        int num1 = scanner.nextInt();
        int num2 = scanner.nextInt();

        // Compute GCD using built-in function
        int gcd = BigInteger.valueOf(num1).gcd(BigInteger.valueOf(num2)).intValue();

        // Compute LCM using formula: LCM(a, b) = (a / GCD) * b
        int lcm = (num1 / gcd) * num2;

        // Output results
        System.out.println("GCD of " + num1 + " and " + num2 + " is: " + gcd);
        System.out.println("LCM of " + num1 + " and " + num2 + " is: " + lcm);

        scanner.close();
    }
}

3. Calculate the LCM and GCD of two numbers Solution Python Try on Compiler 
import math

# Input two numbers
num1, num2 = map(int, input("Enter two numbers: ").split())

# Compute GCD using built-in function
gcd = math.gcd(num1, num2)

# Compute LCM using formula: LCM(a, b) = (a / GCD) * b
lcm = (num1 // gcd) * num2

# Output results
print(f"GCD of {num1} and {num2} is: {gcd}")
print(f"LCM of {num1} and {num2} is: {lcm}")

4. Calculate the LCM and GCD of two numbers Solution Javascript Try on Compiler 
// Function to compute GCD using built-in function (ES6+)
function gcd(a, b) {
    return b === 0 ? a : gcd(b, a % b);
}

// Function to compute LCM
function lcm(a, b) {
    return (a / gcd(a, b)) * b;
}

// Input from user
const readline = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout
});

readline.question("Enter two numbers: ", input => {
    let [num1, num2] = input.split(" ").map(Number);

    // Compute GCD and LCM
    let gcdResult = gcd(num1, num2);
    let lcmResult = lcm(num1, num2);

    // Output results
    console.log(`GCD of ${num1} and ${num2} is: ${gcdResult}`);
    console.log(`LCM of ${num1} and ${num2} is: ${lcmResult}`);

    readline.close();
});

Complexity Analysis for Calculate the LCM and GCD of two numbers Solution

Time Complexity: O(log(min(a, b)))

The time complexity of calculating the GCD using the Euclidean algorithm (as used in the built-in gcd() function) is O(log(min(a, b))). This is because, in each step, the larger number is replaced by its remainder when divided by the smaller number, significantly reducing the problem size. This process continues until the remainder becomes zero, making it much more efficient than the brute-force approach, which has a complexity of O(min(a, b)).

For LCM, the formula LCM(a, b) = (a / GCD) * b is used, which involves just one division and one multiplication. Since these are constant-time operations, the time complexity of computing LCM is O(1). However, since we first compute the GCD in O(log(min(a, b))), the overall complexity of finding both GCD and LCM remains O(log(min(a, b))).

Space Complexity: O(1)

Auxiliary Space Complexity: O(1)
Explanation: The auxiliary space complexity of the built-in GCD function is O(1) because it is implemented iteratively in most programming languages, meaning it does not use recursion and does not require additional stack space. The LCM calculation also operates in O(1) space, as it only involves arithmetic operations without using extra data structures.

Total Space Complexity: O(1)
Explanation: The total space complexity of the algorithm remains O(1) since no additional memory is allocated beyond a few integer variables. Unlike the recursive approach, which has O(log(min(a, b))) space complexity due to the call stack, the built-in function provides an optimized solution with constant space usage.

Real World Example

1. GCD in Real Life: Distributing Items Equally

Imagine you have 24 apples and 36 oranges, and you want to divide them into identical groups with the maximum possible number of fruits in each group.

  • To ensure each group has the same number of apples and oranges, we need to find the Greatest Common Divisor (GCD) of 24 and 36.
  • GCD(24, 36) = 12, meaning we can create 12 groups, each containing 2 apples and 3 oranges.

GCD helps in problems related to equal distribution, arranging items in equal rows, and tiling floors with square tiles of maximum size.

2. LCM in Real Life: Synchronizing Events

Imagine two buses, one arriving at a stop every 6 minutes and the other every 8 minutes. You want to know after how many minutes both buses will arrive together at the stop.

  • This is a case of finding the Least Common Multiple (LCM) of 6 and 8.
  • LCM(6, 8) = 24, meaning the buses will arrive together every 24 minutes.

LCM is useful for scheduling tasks, event synchronization, traffic light coordination, and setting alarms that ring at different intervals.

Similar Problems

Now we have successfully tackled this problem, let's try these similar problems.

1. GCD of two numbers

Given two positive integers a and b, find the GCD of a and b.

Note: Don't use the inbuilt gcd function

2. GCD of digits of a given number

Given a number n, find the GCD of its digits.

💡
Showcase your skills by joining LearnYard Technologies FZ-LLC as a Technical Content Writer. Apply now and inspire the next generation of learners—fill out the form: https://forms.gle/CGDsbGkcapSfvXKM8