【ITニュース解説】Beginner’s Guide for "Replace Non-Coprime Numbers in Array" (LeetCode 2197) with C++, JavaScript & Python Code

今回のテーマは、プログラミングの基礎である配列に関する応用問題、「配列内の互いに素でない数を最小公倍数で置き換える」ことについてだ。この問題は、データ構造の一つである配列の要素を特定のルールに基づいて変換するものであり、システムエンジニアを目指す上で基本的なデータ操作の理解を深める良い機会となるだろう。

具体的には、整数の配列が与えられたとき、隣り合う二つの数が「互いに素でない」場合、その二つの数を削除し、代わりにそれらの「最小公倍数（LCM）」を挿入するという操作を繰り返す。この操作は、もはや隣り合うどの二つの数も互いに素である状態になるまで続けられる。

ここで、「互いに素」という言葉や「最小公倍数」、「最大公約数（GCD）」といった数学的な概念が重要になる。まず、GCDとは、二つの整数を共に割り切る最大の整数を指す。例えば、6と4のGCDは2である。LCMとは、二つの整数のどちらでも割り切れる最小の正の整数を指す。例えば、6と4のLCMは12である。そして、二つの数が「互いに素でない」とは、それらのGCDが1より大きい場合を意味する。つまり、共通の1以外の約数を持つということだ。逆に、GCDが1の場合は「互いに素」である。

この問題の処理の流れを具体的な例で見てみよう。初期配列が[6, 4, 3, 2, 7, 6, 2]である場合を考える。

1. 最初に隣り合う数(6, 4)を見る。6と4のGCDは2であり、1より大きいので互いに素ではない。そこで、これら二つをLCMである12に置き換える。配列は[12, 3, 2, 7, 6, 2]となる。
2. 次に、新しく隣り合った(12, 3)を見る。12と3のGCDは3であり、互いに素ではない。これらをLCMである12に置き換える。配列は[12, 2, 7, 6, 2]となる。
3. さらに隣り合った(12, 2)を見る。12と2のGCDは2であり、互いに素ではない。これらをLCMである12に置き換える。配列は[12, 7, 6, 2]となる。
4. この時点では(12, 7)は互いに素なので何もしない。次に(7, 6)も互いに素なので何もしない。最後に(6, 2)を見る。6と2のGCDは2であり、互いに素ではない。これらをLCMである6に置き換える。配列は[12, 7, 6]となる。
5. 残った(12, 7)と(7, 6)はどちらも互いに素であるため、これ以上置き換えは発生しない。最終結果は[12, 7, 6]となる。

このような操作を効率的に行うためのアルゴリズムとして、「スタック」というデータ構造を利用する方法が考えられる。スタックは、後から入れたものが先に取られる（LIFO: Last-In, First-Out）という特徴を持つ。

アルゴリズムの基本的な考え方はこうだ。まず、空のスタックを用意し、入力配列の各数を順に処理していく。

1. 配列から現在の数を一つ取り出し、スタックの一番上（末尾）に追加する。
2. スタックに二つ以上の要素がある場合、スタックの末尾にある二つの数を取り出し、それらが互いに素であるかどうかをGCDを使ってチェックする。
3. もし互いに素でない場合（GCDが1より大きい場合）、それら二つの数をスタックから取り除き、その二つの数のLCMを計算して、その結果をスタックの末尾に追加する。
4. この「末尾の二つの数をチェックし、互いに素でなければ置き換える」という操作を、スタックの末尾の二つの数が互いに素になるか、あるいはスタックの要素が一つになるまで繰り返す。
5. このプロセスを配列のすべての数に対して行う。すべての数を処理し終えたとき、スタックに残っている要素が最終的な結果となる。

この処理において、GCDの計算にはユークリッドの互除法という効率的な方法が用いられる。LCMは、二つの数aとbがあるとき、LCM(a, b) = (a * b) / GCD(a, b)という関係式で計算できる。この関係式は、二つの数の積をそのGCDで割ることで、最小公倍数を求めることができることを示している。

具体的なコード実装では、C++、JavaScript、Pythonといった様々なプログラミング言語で同様のロジックが適用できる。例えば、C++ではstd::vectorをスタックとして利用し、std::gcd関数でGCDを計算する。JavaScriptでは配列をスタックとして使い、自作のgcd関数で計算する。Pythonではリストをスタックとして使い、math.gcd関数でGCDを計算する。どの言語でも、主要なロジックは「要素をスタックにプッシュし、その後スタックの末尾の二つの要素が互いに素でなくなるまで繰り返しマージする」というパターンに従う。

このアルゴリズムの効率性についても見ていこう。時間計算量と空間計算量という二つの観点から評価する。 時間計算量は、最悪の場合でO(n log(max_value))となる。これは、配列の要素数nに比例して全体の処理が進むこと、そして各要素を処理する際にスタック内で複数のマージが発生する可能性があるが、全体の結合操作の回数はnに制限されるためだ。各結合操作ではGCDの計算が必要であり、GCDの計算には二つの数の値に依存する対数時間（log(max_value)）がかかる。max_valueは配列内の数値の最大値を指す。つまり、要素の数が増えたり、数値が大きくなったりすると、処理時間も増える可能性があるが、効率的に設計されている。

空間計算量はO(n)となる。これは、スタックが最悪の場合、入力配列のすべての要素を保持する可能性があるためだ。スタックに格納される要素の数は、入力配列の要素数nに比例する。

この問題を通じて、いくつかの重要なポイントがわかる。 まず、スタックのような適切なデータ構造を選ぶことが、複雑な問題を効率的に解決する上で非常に役立つという点だ。スタックのLIFO特性が、常に最新の隣接要素に注目し、結合を繰り返すこの問題に最適に機能する。 次に、GCDとLCMといった基本的な数学的ツールが、プログラミング問題の解決において不可欠な役割を果たすという点だ。これらの概念を理解し、適切に利用することが、論理的思考力を養う上でも重要になる。 そして、この問題では、最終的な結果が操作の順序に依存せず一意に定まるという特性も興味深い。どの隣接する非互いに素なペアを先に処理しても、最終的な配列は同じになる。これは、アルゴリズムの正当性を保証する上で重要な性質だ。 このように、数学的な特性とデータ構造の組み合わせは、現実世界の様々な問題を解決するための強力なアプローチを提供してくれる。