LeetCode - Find Greatest Common Divisor of Array をSwiftで解説する

• 元の問題は英語なので、代わりに翻訳したものを記載しています。
• 回答はあくまでも例であり、他の方法も存在します。

前置き

Swiftで最大公約数を求める実装を学ぶことができます。

問題

問題	難易度
Find Greatest Common Divisor of Array	easy

整数配列numsが与えられたとき、nums内の最小の数と最大の数の最大公約数を返します。
2つの数値の最大公約数とは、両方の数値を均等に分割する最大の正の整数のことです。

補足として、以下のようなテストケースが与えられます。

ex1
Input: nums = [2,5,6,9,10]
Output: 2

ex2
Input: nums = [7,5,6,8,3]
Output: 1

ex3
Input: nums = [3,3]
Output: 3

答え

ユークリッドの互除法 を用いる

ユークリッドの互除法とは？

2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。

（引用：ユークリッドの互除法）

文章だとわかりづらいですが、以下の例がわかりやすいでしょう。

(引用：ユークリッドの互除法まとめ（証明・最大公約数・不定方程式）

これをコードに直すことで求めることができます。

解法

func findGCD(_ nums: [Int]) -> Int {
    var maximum = nums[0], minimum = nums[0]

    // 最小値と最大値を求める
    for num in nums {
        if maximum < num {
            maximum = num
        } else if num < minimum {
            minimum = num
        }
    }

    // 「ユークリッドの互除法」で余りが「０」となる場合を求める
    while maximum % minimum != 0 {
        let result = maximum % minimum
        maximum = minimum
        minimum = result
    }

    return minimum
}

最小値と最大値はあえて愚直に線形探索して求めましたが、Swift の デフォルトの API を使用するとすぐに求めることができます。

func findGCD(_ nums: [Int]) -> Int {
    var maximum = nums.max()!, minimum = nums.min()!

    while maximum % minimum != 0 {
        let result = maximum % minimum
        maximum = minimum
        minimum = result
    }

    return minimum
}

実行結果

Runtime	Memory
32ms~	14MB前後

その他

Swift で最大公約数を求めるシンプルな関数です。

func gcd(_ num1: Int, _ num2: Int) -> Int {
   let r = num1 % num2
   if r != 0 {
       return gcd(num2, r)
   } else {
       return num2
   }
}

（引用：コーディングテストとか競技プログラミングとかで役立ちそうな関数）

いっけんすると何をしているのかとなりそうですが、ベースの考え方はユークリッドの互除法であり、それを簡潔にしたものとなっています。

再起関数で０になるまで実行し、最大公約数を求めています。