Swift Coding Test Course, Finding the Greatest Common Divisor

Hello! Today, I will conduct a coding test lecture for developers preparing for job applications using Swift. The topic of this session is Greatest Common Divisor (GCD). The greatest common divisor is the largest number among the common divisors of two numbers and is used in various algorithm problems in addition to its mathematical concept.

Problem Description

Write a function in Swift that finds the greatest common divisor of the given two integers a and b. Additionally, if both numbers are 0, it should output a message saying ‘undefined’.

func gcd(_ a: Int, _ b: Int) -> String

Problem-Solving Approach

There are various methods to find the greatest common divisor, but the most commonly used method is the Euclidean algorithm. This algorithm is based on the following two simple facts:

  • The greatest common divisor of two numbers a and b is gcd(a, 0) = |a|.
  • The greatest common divisor of two numbers a and b is gcd(a, b) = gcd(b, a % b).

Implementation of the Euclidean Algorithm

Based on the two principles above, I will explain step by step how to apply the Euclidean algorithm to find the greatest common divisor.

Step 1: Function Definition

First, define a function that takes two integers and returns the greatest common divisor. The function signature is as follows:

func gcd(_ a: Int, _ b: Int) -> String

Step 2: Input Validation

Inside the function, check if both input values are 0. In this case, return the message ‘undefined’:

if a == 0 && b == 0 {
        return "undefined"
    }

Step 3: Algorithm Implementation

Use the Euclidean algorithm to iteratively calculate the greatest common divisor. In this process, swap the two numbers and use the remainder to update the values:

var a = abs(a)
    var b = abs(b)

    while b != 0 {
        let temp = b
        b = a % b
        a = temp
    }
    return String(a)

Step 4: Completing the Full Code

Integrating all the steps above, we can complete the final greatest common divisor function:

func gcd(_ a: Int, _ b: Int) -> String {
        if a == 0 && b == 0 {
            return "undefined"
        }
        var a = abs(a)
        var b = abs(b)

        while b != 0 {
            let temp = b
            b = a % b
            a = temp
        }
        return String(a)
    }

Test Cases

Now, let’s validate the greatest common divisor function we have written with various test cases. Below are some example test cases:

print(gcd(48, 18)) // Output: 6
print(gcd(0, 0)) // Output: undefined
print(gcd(56, 98)) // Output: 14

Conclusion

In this lecture, we covered an algorithm problem to find the greatest common divisor using Swift. We were able to write concise and efficient code following the principles of the Euclidean algorithm. Algorithm problems can be further developed through understanding mathematical principles and practicing implementing them in programming. We will continue to conduct coding test lectures on various topics, so please stay tuned!

© 2023 Algorithm Problem Solving Course