Javascript Coding Test Course, Finding the Greatest Common Divisor

Topic: Finding the Greatest Common Divisor

Problem Description

Write a function that calculates the greatest common divisor (GCD) of two given integers a and b.
The greatest common divisor is the largest number that divides both numbers.

Input and Output Format

  • Input: Two positive integers a, b (1 ≤ a, b ≤ 109)
  • Output: The greatest common divisor of the two numbers

Example

        Input: 48, 18
        Output: 6

Approach to the Problem

There are various methods to find the greatest common divisor, but utilizing the famous Euclidean Algorithm can solve it efficiently.
This algorithm is based on the following principle:

  • The GCD of two integers a and b can be found by repeatedly calculating a % b until b becomes 0.
  • That is, GCD(a, b) = GCD(b, a % b), and when b becomes 0, a is the greatest common divisor.

Explanation of the Euclidean Algorithm

The Euclidean algorithm operates in the following steps:

  1. Prepare a and b. If b is not 0, proceed to the next step.
  2. Calculate r = a % b to obtain the new remainder.
  3. Update the value of a to b, and the value of b to r.
  4. Repeat this process until b becomes 0.
  5. As a result, a will be the greatest common divisor.

JavaScript Implementation

The code implementing the Euclidean algorithm in JavaScript is as follows:

        function gcd(a, b) {
            while (b !== 0) {
                const r = a % b;
                a = b;
                b = r;
            }
            return a;
        }

        // Test
        const result = gcd(48, 18);
        console.log(result); // 6

Time Complexity Analysis

The time complexity of the Euclidean algorithm is O(log(min(a, b))).
The performance is generally good depending on the ratio of the two numbers, and it is particularly efficient when dealing with large numbers.

Additional Problems and Exercises

If you are comfortable with finding the greatest common divisor, try solving the following problems:

  • Write a function to calculate the least common multiple when given two integers. (Use the fact that LCM(a, b) = a * b / GCD(a, b).)
  • Write a function to find the greatest common divisor of all elements in a given array.

Conclusion

In this article, we explored how to solve the problem of finding the greatest common divisor using JavaScript.
We learned an efficient approach through the Euclidean algorithm.
Such fundamental algorithms are frequently used in coding tests and practical applications, so thorough practice is essential.

References