Python Coding Test Course, Finding the Least Common Multiple

Hello! In this post, we will take a detailed look at how to calculate the ‘Least Common Multiple (LCM)’ through solving algorithmic problems. The least common multiple is the smallest number among the common multiples of two or more integers. It is important to thoroughly understand and practice this problem as it frequently appears in programming interviews and coding tests.

Problem Definition

Write a function to find the least common multiple of the two given integers A and B.

Input

  • Two integers A and B (1 ≤ A, B ≤ 100,000)

Output

  • The least common multiple (LCM) of A and B

Example

Input: 
4 5

Output: 
20

Problem Approach

To calculate the least common multiple, it is efficient to utilize the Greatest Common Divisor (GCD). The least common multiple can be obtained using the following formula:

LCM(A, B) = (A × B) / GCD(A, B)

The origin of this formula comes from the definition of multiples of two numbers and the properties of the greatest common divisor. Dividing the product of the two numbers by the greatest common divisor leaves only the multiples that those numbers do not share.

Calculating GCD in Python

In Python, you can easily find the greatest common divisor by using the built-in math module.

Writing Code to Solve the Problem

Now, let’s implement a function to calculate the least common multiple step by step.

import math

def lcm(a: int, b: int) -> int:
    return (a * b) // math.gcd(a, b)

# Test the function
a, b = map(int, input("Enter two integers: ").split())
print(f"The least common multiple of {a} and {b} is {lcm(a, b)}.")

Code Explanation

  • First, we import the math module to use the gcd function.
  • We define the lcm function, which takes two integers as parameters and returns the least common multiple.
  • Finally, we take user input to test the function.

Test Cases

Now, let’s verify if the function works correctly with various input values.

# Test Cases
print(lcm(4, 5))  # Output: 20
print(lcm(12, 15))  # Output: 60
print(lcm(7, 3))  # Output: 21
print(lcm(100, 10))  # Output: 100
print(lcm(27, 36))  # Output: 108

Complexity Analysis

Now let’s analyze the time and space complexity of the code.

  • Time Complexity: By using the Euclidean algorithm to calculate the GCD, it has a time complexity of O(log(min(A, B))). Thus, the overall complexity of finding the LCM is also O(log(min(A, B))).
  • Space Complexity: Constant space O(1) as it does not use any additional memory.

Conclusion

In this post, we implemented an algorithm to find the least common multiple of two numbers using Python. This problem has been a great opportunity to review the concepts of divisors and multiples. It is a common type that appears in coding tests, so I encourage you to practice thoroughly.

In the next post, I will come back with a wider variety of problems. Thank you for your interest!

References