GCD & LCM Applications

▶

Steps

setup

Initialize variables a and b

Set initial values of a and b to 12 and 18 respectively, preparing for the Euclidean algorithm.

💡 Initialization sets the starting point for the algorithm, making clear which values will be manipulated.

Line:

a, b = 12, 18

💡 The algorithm begins with the original input values stored in variables a and b.

compare

Check if b is zero to continue loop

Evaluate the condition 'b != 0' to decide whether to enter the Euclidean algorithm loop.

💡 This condition controls the loop; if b is zero, the GCD is found.

Line:

while b != 0:

💡 Since b is 18, the loop will execute to reduce the values.

shrink

Update a and b: a becomes b, b becomes a mod b

Assign a the value of b (18), and b the value of a % b (12 % 18 = 12).

💡 This step reduces the problem size by replacing a and b with smaller values, moving towards the GCD.

Line:

a, b = b, a % b

💡 Swapping and modulo operation progress the Euclidean algorithm by reducing b.

compare

Check if b is zero to continue loop

Evaluate 'b != 0' with b = 12 to decide if the loop continues.

💡 The loop continues as long as b is not zero, ensuring the algorithm progresses.

Line:

while b != 0:

💡 b is 12, so the algorithm will perform another iteration.

shrink

Update a and b: a becomes b, b becomes a mod b

Assign a the value of b (12), and b the value of a % b (18 % 12 = 6).

💡 This iteration further reduces the values, moving closer to the GCD.

Line:

a, b = b, a % b

💡 Modulo operation reduces b from 12 to 6, progressing the algorithm.

compare

Check if b is zero to continue loop

Evaluate 'b != 0' with b = 6 to decide if the loop continues.

💡 The loop continues until b becomes zero, indicating the GCD is found.

Line:

while b != 0:

💡 b is 6, so the algorithm will perform another iteration.

shrink

Update a and b: a becomes b, b becomes a mod b

Assign a the value of b (6), and b the value of a % b (12 % 6 = 0).

💡 This step reduces b to zero, signaling the end of the Euclidean algorithm loop.

Line:

a, b = b, a % b

💡 When b becomes zero, a holds the GCD.

compare

Check if b is zero to exit loop

Evaluate 'b != 0' with b = 0 to decide if the loop should terminate.

💡 The loop ends when b is zero, confirming the GCD is found.

Line:

while b != 0:

💡 b is zero, so the algorithm stops and a contains the GCD.

record

Store GCD result

Assign the final value of a (6) as the GCD of the original inputs.

💡 Recording the GCD allows it to be used for the LCM calculation.

Line:

gcd = gcd_iterative(a_original, b_original)

💡 The GCD is the largest number dividing both inputs without remainder.

insert

Calculate LCM using overflow-safe formula

Compute LCM as (a_original / GCD) * b_original = (12 / 6) * 18 = 2 * 18 = 36.

💡 Using division before multiplication avoids overflow and ensures correct LCM calculation.

Line:

lcm = a_original // gcd * b_original

💡 LCM is the smallest number divisible by both original inputs, calculated safely.

reconstruct

Output final results

Print the GCD and LCM values: GCD = 6, LCM = 36.

💡 Displaying results confirms the algorithm's correctness and completes the process.

Line:

print("GCD =", gcd)
print("LCM =", lcm)

💡 The final output matches the expected mathematical results for the inputs.

def gcd_iterative(a, b):  # STEP 1
    while b != 0:  # STEP 2,4,6,8
        a, b = b, a % b  # STEP 3,5,7
    return a  # STEP 9

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

if __name__ == '__main__':  # STEP 1
    a, b = 12, 18
    gcd = gcd_iterative(a, b)  # STEP 9
    lcm = lcm_safe(a, b)  # STEP 10
    print("GCD =", gcd)  # STEP 11
    print("LCM =", lcm)  # STEP 11

📊

GCD & LCM Applications - Watch the Algorithm Execute, Step by Step

Watching each update to a and b reveals how the Euclidean algorithm efficiently reduces the problem size until the GCD is found, making the process intuitive.

setup

a

12

0

b

18

1

compare

a

12

0

b

18

1

move_left

a

18

0

b

12

1

compare

a

18

0

b

12

1

move_left

a

12

0

b

6

1

compare

a

12

0

b

6

1

move_left

a

6

0

b

0

1

compare

a

6

0

b

0

1

Result: 6

record

a

6

0

b

0

1

Result: 6

insert

GCD

6

0

LCM

36

1

Result: {"GCD":6,"LCM":36}

record

GCD

6

0

LCM

36

1

Result: {"GCD":6,"LCM":36}

Key Takeaways

✓ The Euclidean algorithm efficiently finds the GCD by iteratively replacing (a, b) with (b, a mod b) until b is zero.

This iterative reduction is hard to visualize from code alone but becomes clear when watching the values update step-by-step.

✓ Calculating LCM as (a_original / GCD) * b_original avoids overflow and ensures correctness.

The order of operations in LCM calculation is subtle and often overlooked without a careful trace.

✓ Each iteration's update to a and b shows how the problem size shrinks, making the algorithm's termination condition intuitive.

Seeing the pointers move and values change concretely demonstrates why the loop eventually ends.

Practice

1. Consider the following Python code that checks if a number is happy using a known unhappy cycle set. What is the output when the input is 7?

def isHappy(n: int) -> bool:
    unhappy_cycle = {4, 16, 37, 58, 89, 145, 42, 20}

    def digit_square_sum(num: int) -> int:
        total = 0
        while num > 0:
            digit = num % 10
            total += digit * digit
            num //= 10
        return total

    while n != 1 and n not in unhappy_cycle:
        n = digit_square_sum(n)
    return n == 1

print(isHappy(7))

easy

A. True

B. False

C. The code runs indefinitely (infinite loop)

D. Raises an exception

Solution

1. Step 1: Trace digit_square_sum for input 7

   7 -> 7² = 49; next iteration: 4² + 9² = 16 + 81 = 97; then 9² + 7² = 81 + 49 = 130; then 1² + 3² + 0² = 1 + 9 + 0 = 10; then 1² + 0² = 1 + 0 = 1.

2. Step 2: Check loop termination condition

   Since n reaches 1, the loop exits and returns True.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   7 is a known happy number and code returns True [OK]

Hint: 7 leads to 1 after sum-of-squares iterations [OK]

Common Mistakes:

• Confusing unhappy cycle detection
• Miscomputing digit squares
• Assuming infinite loop

2. You are given a list of points on a 2D plane. Your task is to find the rectangle with the minimum area such that all four corners are points from the list. Which approach guarantees finding the optimal solution efficiently?

easy

A. Use a hash set to store points and check pairs of points as diagonals to find rectangles.

B. Use dynamic programming to build rectangles from smaller sub-rectangles.

C. Use a greedy approach by sorting points and selecting closest pairs to form rectangles.

D. Use a brute force approach checking all quadruples of points to find rectangles.

Solution

1. Step 1: Understand the problem constraints

   The problem requires finding rectangles formed by points with minimum area, which involves checking pairs of points as potential diagonals.

2. Step 2: Evaluate approaches

   Brute force (checking all quadruples) is correct but inefficient (O(n^4)). Greedy and DP approaches do not guarantee correctness or efficiency here. Using a hash set to check existence of complementary points for diagonals is both correct and efficient (O(n^2)).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set + diagonal pairs -> optimal and correct [OK]

Hint: Hash set + diagonal pairs is key [OK]

Common Mistakes:

• Thinking greedy or DP solves this efficiently
• Using brute force without pruning

3. 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

4. Suppose the problem is modified so that points can be reused multiple times (i.e., infinite copies of each point are available). Which of the following changes to the algorithm is necessary to correctly find the maximum number of points on a line under this new constraint?

hard

A. No change needed; the original algorithm already accounts for duplicates and infinite reuse.

B. Change the approach to use a mathematical formula for infinite geometric progressions instead of slope counting.

C. Modify the algorithm to consider infinite multiplicity by counting points with the same coordinates once and multiplying by the number of allowed uses.

D. The problem reduces to checking if any line passes through at least one point, so return the total number of points.

Solution

1. Step 1: Understand infinite reuse impact

   Infinite copies mean duplicates can be counted multiple times, so counting duplicates once is insufficient.

2. Step 2: Modify counting to multiply duplicates by allowed reuse

   The algorithm must track multiplicity and multiply counts accordingly to reflect infinite reuse.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Original algorithm counts duplicates once; infinite reuse requires multiplicative counting [OK]

Hint: Infinite reuse requires multiplicative counting of duplicates [OK]

Common Mistakes:

• Assuming original algorithm handles infinite reuse
• Ignoring multiplicity effects

5. Suppose the problem is modified so that points can have negative coordinates and the input size is very large. Which modification to the optimal approach is necessary to maintain efficiency and correctness?

hard

A. Use a hash set as before, since it supports negative coordinates and lookups remain O(1).

B. Replace the hash set with a balanced binary search tree to handle negative coordinates efficiently.

C. Sort points by coordinates and use two pointers to find rectangles, avoiding hash sets.

D. Switch to brute force checking all quadruples since negative coordinates break the hash set approach.

Solution

1. Step 1: Consider data structure requirements

   Hash sets in Python support negative integers as keys with O(1) average lookup time.

2. Step 2: Evaluate alternatives

   Replacing with balanced trees adds unnecessary overhead; sorting and two pointers do not guarantee rectangle detection efficiently; brute force is too slow.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Hash set handles negative coords efficiently -> no change needed [OK]

Hint: Hash sets handle negative keys naturally [OK]

Common Mistakes:

• Thinking hash sets can't handle negative keys
• Switching to slower data structures unnecessarily