GCD & LCM Applications

🎯

GCD & LCM Applications

easyMATHAmazonGoogle

Imagine you are organizing two different events that repeat every few days, and you want to find when both events coincide again. This problem helps you find that timing using GCD and LCM.

💡 This problem involves understanding the relationship between the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of two numbers. Beginners often struggle because they try to compute LCM directly without leveraging the GCD, which is more efficient and mathematically elegant.

📋

Problem Statement

Given two positive integers, compute their Greatest Common Divisor (GCD) and Least Common Multiple (LCM). Input consists of two integers a and b. Output the GCD and LCM of these two numbers.

1 ≤ a, b ≤ 10^9

💡

Example

Input"a = 12, b = 18"

OutputGCD = 6, LCM = 36

The largest number dividing both 12 and 18 is 6. The smallest number divisible by both is 36.

• a = 1, b = 1 → GCD = 1, LCM = 1
• a = 1, b = 10^9 → GCD = 1, LCM = 10^9
• a = 10^9, b = 10^9 → GCD = 10^9, LCM = 10^9
• a = prime number, b = multiple of that prime → GCD = prime, LCM = b

⚠️

Common Mistakes

Computing LCM as a * b without dividing by GCD

Causes integer overflow or incorrect LCM values

✅ Always compute LCM as (a / GCD) * b to avoid overflow

Using recursion without base case in Euclidean algorithm

Leads to infinite recursion and stack overflow

✅ Include base case: if b == 0, return a

Using brute force approach for large inputs

Time limit exceeded or very slow performance

✅ Use Euclidean algorithm for efficient GCD calculation

Not handling the case when a or b is 1

Incorrect GCD or LCM calculation

✅ Ensure code correctly handles smallest inputs

Integer division errors in languages like Java or C++

Incorrect LCM due to truncation

✅ Cast to long or use long long before division and multiplication

🧠

Brute Force (Iterative GCD & LCM Calculation)

💡 This approach exists to build intuition about what GCD and LCM mean by directly checking divisors and multiples. It is slow but conceptually straightforward.

Intuition

To find the GCD, check all numbers from min(a, b) down to 1 to find the largest divisor of both. For LCM, check multiples of max(a, b) upwards until one is divisible by both.

Algorithm

1. Find the minimum of a and b.
2. Iterate downwards from min(a, b) to 1 to find the largest number dividing both a and b (GCD).
3. Find the maximum of a and b.
4. Iterate upwards from max(a, b) to a*b to find the smallest number divisible by both a and b (LCM).

💡 This approach is easy to understand but inefficient, especially for large inputs, because it checks many unnecessary candidates.

</>

Code

def gcd_brute_force(a, b):
    gcd = 1
    for i in range(min(a, b), 0, -1):
        if a % i == 0 and b % i == 0:
            gcd = i
            break
    return gcd

def lcm_brute_force(a, b):
    lcm = max(a, b)
    while True:
        if lcm % a == 0 and lcm % b == 0:
            return lcm
        lcm += 1

if __name__ == '__main__':
    a, b = 12, 18
    print("GCD =", gcd_brute_force(a, b))
    print("LCM =", lcm_brute_force(a, b))

Line Notes

for i in range(min(a, b), 0, -1):Iterate downwards from the smaller number to find the largest common divisor

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

while True:Start an infinite loop to find the LCM by checking multiples

if lcm % a == 0 and lcm % b == 0:Check if current lcm candidate is divisible by both numbers

public class GcdLcmBruteForce {
    public static int gcd(int a, int b) {
        int gcd = 1;
        for (int i = Math.min(a, b); i >= 1; i--) {
            if (a % i == 0 && b % i == 0) {
                gcd = i;
                break;
            }
        }
        return gcd;
    }

    public static int lcm(int a, int b) {
        int lcm = Math.max(a, b);
        while (true) {
            if (lcm % a == 0 && lcm % b == 0) {
                return lcm;
            }
            lcm++;
        }
    }

    public static void main(String[] args) {
        int a = 12, b = 18;
        System.out.println("GCD = " + gcd(a, b));
        System.out.println("LCM = " + lcm(a, b));
    }
}

Line Notes

for (int i = Math.min(a, b); i >= 1; i--) {Loop downwards from smaller number to find GCD

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

while (true) {Infinite loop to find LCM by checking multiples

if (lcm % a == 0 && lcm % b == 0) {Check if current candidate is divisible by both

#include <iostream>
#include <algorithm>
using namespace std;

int gcd_brute_force(int a, int b) {
    int gcd = 1;
    for (int i = min(a, b); i >= 1; i--) {
        if (a % i == 0 && b % i == 0) {
            gcd = i;
            break;
        }
    }
    return gcd;
}

int lcm_brute_force(int a, int b) {
    int lcm = max(a, b);
    while (true) {
        if (lcm % a == 0 && lcm % b == 0) {
            return lcm;
        }
        lcm++;
    }
}

int main() {
    int a = 12, b = 18;
    cout << "GCD = " << gcd_brute_force(a, b) << endl;
    cout << "LCM = " << lcm_brute_force(a, b) << endl;
    return 0;
}

Line Notes

for (int i = min(a, b); i >= 1; i--) {Loop downwards from smaller number to find GCD

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

while (true) {Infinite loop to find LCM by checking multiples

if (lcm % a == 0 && lcm % b == 0) {Check if current candidate is divisible by both

function gcdBruteForce(a, b) {
    let gcd = 1;
    for (let i = Math.min(a, b); i >= 1; i--) {
        if (a % i === 0 && b % i === 0) {
            gcd = i;
            break;
        }
    }
    return gcd;
}

function lcmBruteForce(a, b) {
    let lcm = Math.max(a, b);
    while (true) {
        if (lcm % a === 0 && lcm % b === 0) {
            return lcm;
        }
        lcm++;
    }
}

// Example usage
const a = 12, b = 18;
console.log("GCD =", gcdBruteForce(a, b));
console.log("LCM =", lcmBruteForce(a, b));

Line Notes

for (let i = Math.min(a, b); i >= 1; i--) {Loop downwards from smaller number to find GCD

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

while (true) {Infinite loop to find LCM by checking multiples

if (lcm % a === 0 && lcm % b === 0) {Check if current candidate is divisible by both

⏱

Complexity

TimeO(min(a,b) + (a*b - max(a,b)))

SpaceO(1)

GCD loop runs up to min(a,b), LCM loop can run up to a*b in worst case, which is very large.

💡 For a=12 and b=18, this means up to 12 iterations for GCD and potentially many for LCM, which is inefficient for large inputs.

Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but helps understand the problem and verify correctness on small inputs.

🧠

Euclidean Algorithm for GCD and LCM from GCD

💡 This approach uses the efficient Euclidean algorithm to compute GCD, then derives LCM using the formula LCM(a,b) = (a*b)/GCD(a,b). It is much faster and commonly used in interviews.

Intuition

The Euclidean algorithm reduces the problem of finding GCD by repeatedly replacing the larger number by its remainder when divided by the smaller number until zero is reached. LCM can then be computed using the relationship with GCD.

Algorithm

1. If b is zero, return a as GCD.
2. Otherwise, recursively compute GCD(b, a mod b).
3. Compute LCM as (a * b) divided by GCD.
4. Return both GCD and LCM.

💡 The recursive step reduces the problem size quickly, making it efficient even for large inputs.

</>

Code

def gcd_euclidean(a, b):
    if b == 0:
        return a
    return gcd_euclidean(b, a % b)

def lcm_from_gcd(a, b):
    gcd = gcd_euclidean(a, b)
    return a // gcd * b

if __name__ == '__main__':
    a, b = 12, 18
    gcd = gcd_euclidean(a, b)
    lcm = lcm_from_gcd(a, b)
    print("GCD =", gcd)
    print("LCM =", lcm)

Line Notes

if b == 0:Base case: when remainder is zero, current a is the GCD

return gcd_euclidean(b, a % b)Recursive call with smaller problem size

gcd = gcd_euclidean(a, b)Compute GCD using Euclidean algorithm

return a // gcd * bCalculate LCM using the formula to avoid overflow

public class GcdLcmEuclidean {
    public static int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    public static long lcm(int a, int b) {
        int gcd = gcd(a, b);
        return (long) a / gcd * b;
    }

    public static void main(String[] args) {
        int a = 12, b = 18;
        int gcd = gcd(a, b);
        long lcm = lcm(a, b);
        System.out.println("GCD = " + gcd);
        System.out.println("LCM = " + lcm);
    }
}

Line Notes

if (b == 0) return a;Base case for recursion, GCD found

return gcd(b, a % b);Recursive call with remainder

int gcd = gcd(a, b);Compute GCD before LCM calculation

return (long) a / gcd * b;Calculate LCM safely using long to prevent overflow

#include <iostream>
using namespace std;

int gcd_euclidean(int a, int b) {
    if (b == 0) return a;
    return gcd_euclidean(b, a % b);
}

long long lcm_from_gcd(int a, int b) {
    int gcd = gcd_euclidean(a, b);
    return (long long)a / gcd * b;
}

int main() {
    int a = 12, b = 18;
    int gcd = gcd_euclidean(a, b);
    long long lcm = lcm_from_gcd(a, b);
    cout << "GCD = " << gcd << endl;
    cout << "LCM = " << lcm << endl;
    return 0;
}

Line Notes

if (b == 0) return a;Base case for Euclidean recursion

return gcd_euclidean(b, a % b);Recursive call with remainder

int gcd = gcd_euclidean(a, b);Compute GCD before LCM

return (long long)a / gcd * b;Calculate LCM using long long to avoid overflow

function gcdEuclidean(a, b) {
    if (b === 0) return a;
    return gcdEuclidean(b, a % b);
}

function lcmFromGcd(a, b) {
    const gcd = gcdEuclidean(a, b);
    return (a / gcd) * b;
}

// Example usage
const a = 12, b = 18;
console.log("GCD =", gcdEuclidean(a, b));
console.log("LCM =", lcmFromGcd(a, b));

Line Notes

if (b === 0) return a;Base case for recursion, GCD found

return gcdEuclidean(b, a % b);Recursive call with remainder

const gcd = gcdEuclidean(a, b);Compute GCD before LCM

return (a / gcd) * b;Calculate LCM using the formula

⏱

Complexity

TimeO(log(min(a,b)))

SpaceO(log(min(a,b))) due to recursion stack

Euclidean algorithm reduces problem size quickly by modulo operation, leading to logarithmic time complexity.

💡 For inputs up to 10^9, this means only about 30 recursive calls, which is very efficient.

Interview Verdict: Accepted

This is the standard and efficient approach expected in interviews for GCD and LCM problems.

🧠

Iterative Euclidean Algorithm with Overflow-Safe LCM

💡 This approach uses an iterative version of the Euclidean algorithm to avoid recursion stack overhead and carefully computes LCM to prevent integer overflow.

Intuition

Instead of recursion, use a loop to compute GCD. Then compute LCM using a safe multiplication order to avoid overflow.

Algorithm

1. Initialize variables a and b.
2. While b is not zero, replace a with b and b with a mod b.
3. After loop ends, a contains the GCD.
4. Compute LCM as (a_original / GCD) * b_original to avoid overflow.

💡 The iterative loop is easier to understand and safer in languages with limited recursion depth.

</>

Code

def gcd_iterative(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def lcm_safe(a, b):
    gcd = gcd_iterative(a, b)
    return a // gcd * b

if __name__ == '__main__':
    a, b = 12, 18
    gcd = gcd_iterative(a, b)
    lcm = lcm_safe(a, b)
    print("GCD =", gcd)
    print("LCM =", lcm)

Line Notes

while b != 0:Loop until remainder is zero

a, b = b, a % bUpdate a and b to next step in Euclidean algorithm

return aReturn the GCD after loop ends

return a // gcd * bCalculate LCM safely using integer division first

public class GcdLcmIterative {
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

    public static long lcm(int a, int b) {
        int gcd = gcd(a, b);
        return (long) a / gcd * b;
    }

    public static void main(String[] args) {
        int a = 12, b = 18;
        int gcd = gcd(a, b);
        long lcm = lcm(a, b);
        System.out.println("GCD = " + gcd);
        System.out.println("LCM = " + lcm);
    }
}

Line Notes

while (b != 0) {Loop until remainder is zero

int temp = b;Store current b temporarily

b = a % b;Update b to remainder

a = temp;Update a to previous b

#include <iostream>
using namespace std;

int gcd_iterative(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

long long lcm_safe(int a, int b) {
    int gcd = gcd_iterative(a, b);
    return (long long)a / gcd * b;
}

int main() {
    int a = 12, b = 18;
    int gcd = gcd_iterative(a, b);
    long long lcm = lcm_safe(a, b);
    cout << "GCD = " << gcd << endl;
    cout << "LCM = " << lcm << endl;
    return 0;
}

Line Notes

while (b != 0) {Loop until remainder is zero

int temp = b;Temporarily store b

b = a % b;Update b to remainder

a = temp;Update a to previous b

function gcdIterative(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

function lcmSafe(a, b) {
    const gcd = gcdIterative(a, b);
    return (a / gcd) * b;
}

// Example usage
const a = 12, b = 18;
console.log("GCD =", gcdIterative(a, b));
console.log("LCM =", lcmSafe(a, b));

Line Notes

while (b !== 0) {Loop until remainder is zero

let temp = b;Store current b temporarily

b = a % b;Update b to remainder

a = temp;Update a to previous b

⏱

Complexity

TimeO(log(min(a,b)))

SpaceO(1)

Iterative Euclidean algorithm avoids recursion overhead and runs in logarithmic time.

💡 This approach is efficient and safe for large inputs without risking stack overflow.

Interview Verdict: Accepted

This is a robust approach suitable for production code and interviews.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, you should code the Euclidean algorithm approach (Approach 2 or 3) because it is efficient, clean, and widely accepted.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(min(a,b) + a*b)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Recursive Euclidean Algorithm	O(log(min(a,b)))	O(log(min(a,b))) due to recursion stack	Yes (deep recursion for very large inputs)	N/A	Preferred approach, clean and efficient
3. Iterative Euclidean Algorithm	O(log(min(a,b)))	O(1)	No	N/A	Best for production code, avoids recursion overhead

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding, and finally present the optimal Euclidean algorithm solution.

How to Present

Step 1: Clarify the input constraints and what GCD and LCM mean.Step 2: Describe the brute force approach to find GCD and LCM by checking divisors and multiples.Step 3: Explain the Euclidean algorithm for efficient GCD calculation.Step 4: Show how to compute LCM using the GCD to avoid redundant calculations.Step 5: Discuss iterative vs recursive implementations and overflow considerations.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 5min → Test: 5min. Total ~15min

What the Interviewer Tests

The interviewer tests your understanding of number theory basics, ability to optimize naive solutions, and knowledge of the Euclidean algorithm and its applications.

Common Follow-ups

• How to compute GCD and LCM for multiple numbers? → Use pairwise GCD and LCM iteratively.
• What if numbers are very large (beyond 64-bit)? → Use BigInteger or implement binary GCD algorithm.

💡 These follow-ups test your ability to generalize the solution and handle edge cases in real-world scenarios.

🔍

Pattern Recognition

When to Use

1) Problem involves two or more integers; 2) Need to find common divisors or multiples; 3) Constraints allow efficient GCD computation; 4) LCM is related to GCD.

Signature Phrases

greatest common divisorleast common multipledivisible by bothcommon multiple

NOT This Pattern When

Problems involving prime factorization without GCD/LCM focus or unrelated modular arithmetic problems.

Similar Problems

Greatest Common Divisor of Strings - uses GCD concept on stringsLCM of Two Numbers - direct application of GCD-LCM relationship

Practice

1. You are given a set of points on a 2D plane and need to find the maximum number of points that lie on the same straight line. Which approach guarantees an optimal solution for this problem?

easy

A. Use a greedy approach by sorting points and connecting consecutive points only.

B. Use a divide-and-conquer approach by splitting points into halves and merging results.

C. Use dynamic programming to build up solutions based on subproblems of smaller point sets.

D. Use a nested loop to consider every pair of points, compute slopes as reduced fractions, and count points sharing the same slope from each base point.

Solution

1. Step 1: Understand problem requirements

   The problem requires finding the maximum number of points on a single line, which depends on slopes between points.

2. Step 2: Identify approach that handles all pairs and slope normalization

   Only the nested loop approach with slope normalization (reduced fractions) correctly groups points on the same line and handles duplicates and vertical lines.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Nested loops with slope hashing is the standard optimal approach [OK]

Hint: Check if approach handles all pairs and slope normalization [OK]

Common Mistakes:

• Assuming greedy or DP solves this geometry problem optimally

2. What is the time complexity of answering a single query using the precomputed lookup table approach for the angle between clock hands, assuming the table is already built?

medium

A. O(1) because the angle is retrieved directly from a precomputed 12x60 table.

B. O(12*60) because you must compute all angles each query.

C. O(60) because you must scan all minutes to find the angle.

D. O(log(720)) because binary search is used on the precomputed angles.

Solution

1. Step 1: Understand precomputation

   The table stores angles for all 12 hours and 60 minutes, total 720 entries, computed once.

2. Step 2: Query time complexity

   Each query accesses the table by hour and minute indices directly, which is constant time O(1).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Lookup table access is direct indexing -> O(1) [OK]

Hint: Precomputation shifts cost to setup, queries are O(1) [OK]

Common Mistakes:

• Confusing precomputation cost with query cost
• Assuming linear scan or binary search needed per query

3. The following code attempts to check if two rectangles overlap. Which line contains a subtle bug that causes incorrect results when rectangles only touch at edges or corners?

medium

A. Line 4: Return condition using '>=' instead of '>'

B. Line 2: Calculation of x_overlap

C. Line 1: Function definition

D. Line 3: Calculation of y_overlap

Solution

1. Step 1: Understand overlap condition

   Rectangles overlap only if overlap length on both axes is strictly greater than zero.

2. Step 2: Identify the bug in return condition

   Using '>=' returns true even when rectangles just touch edges (overlap = 0), which is incorrect.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Change '>=' to '>' fixes false positives on touching edges [OK]

Hint: Overlap must be strictly positive, not zero [OK]

Common Mistakes:

• Using '>=' instead of '>' in overlap check
• Mixing up min and max in coordinate calculations
• Ignoring one axis overlap

4. Suppose rectangles can have zero area (width or height zero) and you want to consider touching edges as overlapping. Which modification to the optimal overlap check code correctly implements this?

hard

A. Add a separate check for zero-area rectangles and return true if their edges touch.

B. Ignore zero-area rectangles entirely since they cannot overlap.

C. Use a brute force grid scan to check all points inside the rectangles for overlap.

D. Change the return condition to 'x_overlap >= 0 and y_overlap >= 0' to include touching edges.

Solution

1. Step 1: Understand the new overlap definition

   Touching edges count as overlap, so zero-length overlaps on axes are valid.

2. Step 2: Modify the condition to include zero overlap

   Changing '> 0' to '>= 0' in the return condition correctly includes touching edges.

3. Step 3: Confirm no extra checks needed

   Zero-area rectangles are handled naturally by this condition without extra code.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Using '>=' includes edge-touching cases as overlap [OK]

Hint: Use '>=' to include touching edges as overlap [OK]

Common Mistakes:

• Adding unnecessary complexity for zero-area rectangles
• Ignoring zero-area rectangles leading to incorrect results
• Using brute force which is inefficient

5. Suppose the Roman numeral system is extended to allow repeated symbols beyond the usual limits (e.g., "IIII" for 4 instead of "IV"). Which modification to the optimal single-pass algorithm is necessary to correctly convert such inputs?

hard

A. No modification needed; the existing algorithm handles repeated symbols correctly

B. Use a stack to track symbol sequences and apply custom rules for repeats

C. Add a preprocessing step to convert repeated symbols into subtractive pairs

D. Remove the subtraction logic and always add symbol values

Solution

1. Step 1: Understand the new input format with extended repeats

   Allowing repeated symbols beyond standard subtractive notation breaks assumptions of the original algorithm.

2. Step 2: Identify necessary algorithm change using a stack

   A stack-based approach can track sequences and apply custom rules for repeats and subtractive pairs, handling extended notation correctly.

3. Step 3: Why other options fail

   Always adding values ignores subtraction; preprocessing is complex and inefficient; no modification ignores new rules.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Stack enables flexible parsing of non-standard repeats [OK]

Hint: Extended repeats require tracking sequences, not just pairwise comparison [OK]

Common Mistakes:

• Assuming old logic suffices
• Removing subtraction entirely
• Trying inefficient preprocessing