Kotlin coding test course, finding the least common multiple

One common algorithm problem that frequently appears in coding tests is finding the ‘Least Common Multiple (LCM)’. The least common multiple refers to the smallest common multiple found among the multiples of two given numbers. In this article, we will implement an algorithm to calculate the least common multiple in Kotlin.

Problem Description

Given two integers 𝑎 and 𝑏, please write a function to find their least common multiple. The function signature is as follows:

fun lcm(a: Int, b: Int): Int

For example, the least common multiple of 4 and 6 is 12, and the least common multiple of 15 and 20 is 60. The input range is integers between 1 and 106.

Finding the Least Common Multiple

The least common multiple can be calculated by dividing the product of the two numbers by their greatest common divisor (GCD). The least common multiple is defined by the following formula:

LCM(a, b) = (a * b) / GCD(a, b)

To calculate the least common multiple using the above formula, we must first determine the greatest common divisor of the two numbers. We can use the Euclidean algorithm for this purpose.

Explanation of the Euclidean Algorithm

The Euclidean algorithm is an efficient method to find the greatest common divisor of two numbers. For two numbers 𝑎 and 𝑏, the process proceeds as follows when 𝑏 is not 0:

  1. Find the remainder of 𝑎 divided by 𝑏.
  2. Assign 𝑏 to 𝑎.
  3. Assign the remainder to 𝑏.
  4. Repeat until 𝑏 becomes 0.

Finally, return the value of 𝑎 as the greatest common divisor.

Kotlin Implementation

Now, let’s implement a function in Kotlin to calculate the least common multiple based on the above algorithm.

fun gcd(a: Int, b: Int): Int {
        return if (b == 0) a else gcd(b, a % b)
    }

    fun lcm(a: Int, b: Int): Int {
        return (a * b) / gcd(a, b)
    }
    
    fun main() {
        val a = 4
        val b = 6
        println("Least Common Multiple: ${lcm(a, b)}")  // Output: Least Common Multiple: 12
    }

Function Descriptions

The code above includes two functions:

  1. gcd(a: Int, b: Int): Int – A function that calculates the greatest common divisor. It repeatedly calculates the remainder until it reaches 0.
  2. lcm(a: Int, b: Int): Int – A function that calculates the least common multiple by dividing the product of the two numbers by their greatest common divisor.

Complexity Analysis

The time complexity of the Euclidean algorithm is O(log min(a, b)). This makes it a much faster method for calculating the greatest common divisor based on the size of the two numbers. Therefore, the overall time complexity of the algorithm for finding the least common multiple is also O(log min(a, b)).

Test Cases

Let’s look at some test cases to verify if the function works correctly:

  • lcm(4, 6): 12
  • lcm(15, 20): 60
  • lcm(7, 5): 35
  • lcm(1, 999999): 999999
  • lcm(123456, 789012): 493827156

The results of each function can help validate the correctness of the logic.

Conclusion

We have learned how to solve the problem of finding the least common multiple using Kotlin. We examined how to efficiently calculate the greatest common divisor using the Euclidean algorithm and how to use it to find the least common multiple. Such algorithms frequently appear in coding tests, so it’s advisable to study and practice them thoroughly.