GCD & LCM Applications

📋

Problem

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.

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

Edge cases: a = 1, b = 1 → GCD = 1, LCM = 1a = 1, b = 10^9 → GCD = 1, LCM = 10^9a = 10^9, b = 10^9 → GCD = 10^9, LCM = 10^9

</>

IDE

def gcd_lcm(a: int, b: int) -> list:public int[] gcdLcm(int a, int b)vector<int> gcdLcm(int a, int b)function gcdLcm(a, b)

def gcd_lcm(a, b):
    # Write your solution here
    pass

class Solution {
    public int[] gcdLcm(int a, int b) {
        // Write your solution here
        return new int[]{0, 0};
    }
}

#include <vector>
using namespace std;

vector<int> gcdLcm(int a, int b) {
    // Write your solution here
    return {0, 0};
}

function gcdLcm(a, b) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: [1, 216]Incorrect LCM calculation by naive multiplication without dividing by GCD.✅ Compute LCM as (a*b)//GCD(a,b) instead of a*b directly.

Wrong: [0, 0]Incorrect base case handling or uninitialized variables for GCD and LCM.✅ Initialize GCD to 1 and ensure Euclidean algorithm handles all inputs properly.

Wrong: [7, 147]Incorrect LCM calculation by multiplying without dividing by GCD.✅ Use LCM = (a*b)//GCD to avoid overestimation.

Wrong: TLE or timeoutUsing brute force iteration for GCD and LCM on large inputs.✅ Implement Euclidean algorithm for GCD with O(log(min(a,b))) complexity.

✓

Test Cases

Try testing your solution with minimal and maximal input values to catch edge cases.

Consider special cases like prime multiples and large coprime numbers to find corner cases.

Optimize your solution to handle the largest inputs efficiently using the Euclidean algorithm.

t1_01basic

Input{"a":12,"b":18}

Expected6

⏱ Performance - must finish in 2000ms

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

💡 Recall the Euclidean algorithm for GCD calculation.

💡 Use the formula LCM(a,b) = (a*b)/GCD(a,b) to find LCM efficiently.

💡 Compute GCD first using Euclidean algorithm, then calculate LCM using the formula.

Why it failed: Incorrect GCD or LCM output. Likely cause: not using Euclidean algorithm or incorrect LCM formula. Fix: Implement gcd using Euclidean algorithm and compute lcm as (a*b)//gcd.

✓ Correct GCD and LCM computed using Euclidean algorithm and formula.

t1_02basic

Input{"a":20,"b":30}

Expected10

⏱ Performance - must finish in 2000ms

GCD of 20 and 30 is 10; LCM is (20*30)/10 = 60.

💡 Try to find the largest divisor common to both numbers.

💡 Apply the relationship between GCD and LCM to avoid brute force.

💡 Calculate GCD using Euclidean algorithm, then LCM as (a*b)//GCD.

Why it failed: Wrong output due to brute force or incorrect LCM calculation. Fix by using Euclidean algorithm for GCD and LCM = (a*b)//GCD.

✓ Correctly computed GCD and LCM using efficient method.

t2_01edge

Input{"a":1,"b":1}

Expected1

⏱ Performance - must finish in 2000ms

GCD and LCM of 1 and 1 are both 1.

💡 Check behavior when both inputs are the smallest possible.

💡 GCD(1,1) should be 1; LCM(1,1) should also be 1.

💡 Ensure no division by zero or invalid operations for minimal inputs.

Why it failed: Fails on minimal input: likely division by zero or incorrect base case. Fix: handle a=1 and b=1 explicitly or ensure Euclidean algorithm handles it.

✓ Handles minimal input correctly with GCD=1 and LCM=1.

t2_02edge

Input{"a":1,"b":1000000000}

Expected1

⏱ Performance - must finish in 2000ms

GCD of 1 and 10^9 is 1; LCM is 10^9.

💡 Test with one input as 1 and the other very large.

💡 GCD with 1 should always be 1; LCM equals the other number.

💡 Verify no overflow or performance issues with large input.

Why it failed: Incorrect handling of large input with 1. Possibly overflow or wrong GCD logic. Fix: use Euclidean algorithm and safe multiplication for LCM.

✓ Correctly computes GCD=1 and LCM=10^9 for large input.

t2_03edge

Input{"a":1000000000,"b":1000000000}

Expected1000000000

⏱ Performance - must finish in 2000ms

GCD and LCM of equal large numbers are the number itself.

💡 Check behavior when both inputs are equal and large.

💡 GCD(a,a) = a; LCM(a,a) = a.

💡 Ensure no overflow in LCM calculation when a == b.

Why it failed: Fails on equal large inputs due to overflow or incorrect logic. Fix: handle equal inputs by returning a for both GCD and LCM directly.

✓ Correctly handles equal large inputs with GCD and LCM equal to input.

t3_01corner

Input{"a":7,"b":21}

Expected7

⏱ Performance - must finish in 2000ms

7 is prime and divides 21; GCD=7, LCM=21.

💡 Test with prime number and its multiple.

💡 GCD should be the prime; LCM should be the multiple.

💡 Check that GCD divides both and LCM is computed as (a*b)//GCD.

Why it failed: Fails prime-multiple test by incorrect GCD or LCM. Fix: ensure Euclidean algorithm correctly computes GCD and LCM formula used.

✓ Correctly computes GCD and LCM for prime and multiple.

t3_02corner

Input{"a":1000000000,"b":1}

Expected1

⏱ Performance - must finish in 2000ms

Reverse of edge case: GCD=1, LCM=10^9.

💡 Test reversed large and small inputs.

💡 GCD with 1 is always 1; LCM equals the other number.

💡 Check no assumptions about order of inputs.

Why it failed: Fails reversed input test due to order assumptions. Fix: ensure GCD and LCM calculations are symmetric in inputs.

✓ Handles reversed inputs correctly.

t3_03corner

Input{"a":1000000000,"b":999999937}

Expected1

⏱ Performance - must finish in 2000ms

Two large coprime numbers; GCD=1, LCM=product.

💡 Test with large coprime numbers.

💡 GCD should be 1; LCM is product of both numbers.

💡 Check for overflow-safe multiplication for LCM.

Why it failed: Fails large coprime test due to overflow or incorrect GCD. Fix: use 64-bit integer for multiplication and Euclidean algorithm for GCD.

✓ Correctly computes GCD=1 and LCM as product for large coprimes.

t4_01performance

Input{"a":1000000000,"b":999999937}

Expectednull

⏱ Performance - must finish in 2000ms

Large inputs at constraint boundary; O(log(min(a,b))) Euclidean algorithm must complete within 2s.

💡 Brute force GCD is too slow for large inputs.

💡 Use Euclidean algorithm with O(log(min(a,b))) complexity.

💡 Avoid naive iteration; implement efficient GCD and LCM calculation.

Why it failed: TLE due to brute force or inefficient GCD method. Fix: implement Euclidean algorithm for GCD and use formula for LCM.

✓ Efficient Euclidean algorithm implementation confirmed by passing performance test.

Practice

1. You need to find the smallest angle between the hour and minute hands of a clock given any time. Which approach guarantees an optimal and correct solution for all valid inputs?

easy

A. Use a greedy approach that moves the hour hand in fixed 30-degree increments ignoring minutes.

B. Calculate the exact angles of hour and minute hands considering minute progress, then find the minimal difference.

C. Apply dynamic programming to store intermediate angles for subproblems of time intervals.

D. Use a brute force simulation checking every possible angle from 0 to 360 degrees.

Solution

1. Step 1: Understand the problem requirements

   The problem requires calculating the minimal angle between two clock hands at any given time, which depends on both hour and minute positions.

2. Step 2: Evaluate approaches

   Greedy ignoring minute progress fails for times like 3:30. DP is unnecessary as the problem is direct calculation, and brute force is inefficient. Calculating exact angles considering minute progress ensures correctness.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Minute progress affects hour hand angle -> correct calculation needed [OK]

Hint: Hour hand moves with minutes; ignore minute progress -> wrong [OK]

Common Mistakes:

• Ignoring minute contribution to hour hand angle
• Using greedy increments without minute adjustment

2. Given an integer, determine if it reads the same backward as forward without converting it to a string. Which approach guarantees an optimal solution in terms of time and space complexity?

easy

A. Convert the integer to a string and compare characters from both ends.

B. Use a greedy approach to compare digits from left to right until mismatch.

C. Reverse half of the integer digits and compare with the other half.

D. Use dynamic programming to store palindrome states of digit substrings.

Solution

1. Step 1: Understand the problem constraints

   We want to check if an integer is a palindrome without extra space and efficiently.

2. Step 2: Evaluate approaches

   Converting to string uses extra space; DP is overkill and not applicable; greedy fails on some cases. Reversing half the number uses O(1) space and O(log n) time.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Reversing half the digits avoids overflow and extra space [OK]

Hint: Optimal uses half reversal, not full string conversion [OK]

Common Mistakes:

• Thinking string conversion is optimal
• Using DP unnecessarily
• Greedy fails on middle digits

3. Examine the following buggy code snippet for Max Points on a Line:

from collections import defaultdict
import math

def maxPoints(points):
    n = len(points)
    if n <= 2:
        return n
    max_points = 1
    points.sort()
    for i in range(n):
        if max_points >= n - i or max_points > n // 2:
            break
        slopes = defaultdict(int)
        duplicates = 0
        for j in range(i + 1, n):
            dx = points[j][0] - points[i][0]
            dy = points[j][1] - points[i][1]
            if dx == 0 and dy == 0:
                duplicates += 1
                continue
            gcd = math.gcd(dy, dx)
            if gcd != 0:
                dy //= gcd
                dx //= gcd
            # Bug introduced here: missing normalization of slope sign
            slopes[(dy, dx)] += 1
        curr_max = max(slopes.values(), default=0) + duplicates + 1
        max_points = max(max_points, curr_max)
    return max_points

What is the bug in this code?

medium

A. Line missing slope sign normalization, causing (1,-1) and (-1,1) to be treated differently.

B. Duplicates are not counted, so points with same coordinates are ignored.

C. Vertical lines (dx=0) cause division by zero error.

D. Early termination condition breaks too early, missing maximum points.

Solution

1. Step 1: Identify missing slope sign normalization

   The code does not flip signs when dx < 0, so slopes like (1,-1) and (-1,1) are treated as different lines.

2. Step 2: Understand impact on grouping points

   This causes points on the same line but with opposite slope signs to be counted separately, undercounting max points.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sign normalization is critical to correctly group slopes [OK]

Hint: Check if slope sign normalization is done [OK]

Common Mistakes:

• Ignoring slope sign normalization
• Assuming gcd normalization is enough

4. The following code attempts to check if an integer is a palindrome by reversing half of its digits. Which line contains a subtle bug that causes incorrect results for inputs like 10 or negative numbers?

medium

A. Line 6: return x == reversed_half or x == reversed_half // 10

B. Line 2: reversed_half = 0

C. Line 1: def is_palindrome(x: int) -> bool:

D. Line 3: while x > reversed_half:

Solution

1. Step 1: Identify missing edge case handling

   Negative numbers and numbers ending with zero (except zero itself) are not handled before the loop.

2. Step 2: Analyze loop condition

   Without checking negatives or trailing zeros, the loop condition allows incorrect inputs to proceed, causing wrong results.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Adding pre-check for negatives and trailing zeros before loop fixes bug [OK]

Hint: Check input constraints before main logic to avoid subtle bugs [OK]

Common Mistakes:

• Ignoring negative input check
• Not handling trailing zeros
• Assuming loop condition suffices

5. Consider this buggy recursive reverse integer code snippet:

def reverse(x: int) -> int:
    INT_MAX = 2**31 - 1
    INT_MIN = -2**31
    sign = -1 if x < 0 else 1
    x = abs(x)

    def helper(num, rev):
        if num == 0:
            return rev
        pop = num % 10
        # Bug: Missing overflow check here
        rev = rev * 10 + pop
        return helper(num // 10, rev)

    rev = helper(x, 0)
    return sign * rev if rev != 0 else 0

What is the root cause of incorrect behavior in this code?

medium

A. Line 'rev = rev * 10 + pop' lacks overflow check before multiplication

B. Line with 'sign = -1 if x < 0 else 1' does not handle zero correctly

C. Line 'pop = num % 10' incorrectly extracts digits for negative numbers

D. Line 'return sign * rev if rev != 0 else 0' returns zero incorrectly for valid reversed zero

Solution

1. Step 1: Identify missing overflow check

   The code multiplies rev by 10 and adds pop without checking if rev will overflow 32-bit integer limits.

2. Step 2: Consequence of missing check

   Without overflow check before multiplication, the reversed integer can exceed INT_MAX causing incorrect results or runtime errors.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Overflow check must precede rev update to avoid errors [OK]

Hint: Overflow check must happen before rev update [OK]

Common Mistakes:

• Ignoring overflow before multiplying rev by 10
• Assuming sign handling fixes overflow
• Misunderstanding digit extraction for negatives