C++ Coding Test Course, Euclidean Algorithm

Hello! Today, we will take a look at one of the algorithms frequently tested in coding interviews, the Euclidean algorithm. In this article, we will conceptually understand what the Euclidean algorithm is and explore the process of solving it step by step using a real problem.

What is the Euclidean Algorithm?

The Euclidean algorithm is an efficient algorithm for finding the greatest common divisor (GCD) of two numbers. This method, first introduced by the ancient Greek mathematician Euclid, is very useful because it can determine the GCD through a finite number of operations on the two numbers.

The basic idea of the Euclidean algorithm is as follows:

  • Given two numbers a and b, let r be the remainder when a is divided by b. That is, a = bq + r (where q is the quotient and r is the remainder).
  • Now GCD(a, b) is the same as GCD(b, r). This means we can continue to find the GCD using the remainder.
  • As we repeat this process, there will come a time when r becomes 0, and the b at that time is the GCD.

Example Problem: Finding the Greatest Common Divisor

Now let’s solve a problem using the Euclidean algorithm to find the greatest common divisor.

Problem Description

Given two natural numbers A and B, write a program to find the greatest common divisor of these two numbers.

Input

  • The first line contains the two natural numbers A and B. (1 ≤ A, B ≤ 1,000,000)

Output

  • Output the greatest common divisor of A and B in the first line.

Example

Input:

24 36

Output:

12

Implementation of the Euclidean Algorithm

Now let’s implement the Euclidean algorithm in C++ to solve the above problem. Below is the C++ code.


#include <iostream>

using namespace std;

// Greatest Common Divisor function
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b; // Calculate remainder
        a = b; // Assign b to a
        b = r; // Assign remainder to b
    }
    return a; // Return the greatest common divisor
}

int main() {
    int A, B;
    cout << "Enter A and B: ";
    cin >> A >> B; // Get input for A and B
    cout << "The greatest common divisor is: " << gcd(A, B) << endl; // Print the greatest common divisor
    return 0;
}

Code Explanation

The structure of the above code is as follows:

  • #include <iostream>: This is the header file for using basic input and output functions in C++.
  • using namespace std;: This syntax allows us to use the standard namespace, letting us omit std::.
  • int gcd(int a, int b): This function calculates the greatest common divisor of the two numbers a and b. It calculates r (the remainder) in a loop until b becomes 0.
  • int main(): This is the entry point of the program, responsible for receiving input from the user and printing the greatest common divisor.

Program Execution Process

When the program is compiled and executed, it prompts the user to enter two natural numbers. For instance, if 24 and 36 are entered, the program proceeds as follows:

  1. Initially, a = 24 and b = 36, so r = 24 % 36 = 24.
  2. Now a changes to 36 and b changes to 24. Again, r = 36 % 24 = 12.
  3. Then a changes to 24 and b changes to 12, with r = 24 % 12 = 0.
  4. Since b has become 0, the value of a, which is 12, is printed as the greatest common divisor.

Time Complexity of the Euclidean Algorithm

The time complexity of the Euclidean algorithm is O(log(min(a, b))). This is because when the sizes of the two numbers are similar, at least one of the numbers is reduced by half during each iteration, making it very efficient.

Modified Problem

Now we can modify the Euclidean algorithm to solve other problems. For example, let’s consider a problem of finding the least common multiple (LCM) of two numbers. The least common multiple can be found using the following formula:

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

Implementing this formula in C++ would look like this:


#include <iostream>

using namespace std;

// Greatest Common Divisor function
int gcd(int a, int b) {
    while (b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// Least Common Multiple function
int lcm(int a, int b) {
    return (a * b) / gcd(a, b); // Calculate LCM
}

int main() {
    int A, B;
    cout << "Enter A and B: ";
    cin >> A >> B; // Get input for A and B
    cout << "The least common multiple is: " << lcm(A, B) << endl; // Print LCM
    return 0;
}

Conclusion

In this article, we learned about finding the greatest common divisor and least common multiple using the Euclidean algorithm. This algorithm is efficient and a simple method that can be applied to various problem-solving scenarios. As it is frequently brought up in coding tests, it is important to practice and become familiar with it. We will be covering more problems and algorithms in the future, so please stay tuned! Thank you.