C++ですべての要素を割り切れる配列の要素を見つける方法

いくつかの要素を持つ配列 A があるとします。この中から「他のすべての要素を割り切ることができる」1つの要素を見つけたいと思います。

例として、配列 A = [15, 21, 69, 33, 3, 72, 81] を考えてみましょう。この場合、答えは 3 になります。リスト内のすべての数値が3で割り切れるためです。

解決策のアプローチ

この問題は、以下の手順でシンプルに解くことができます。

1. まず、配列内の最小値を求めます。
2. 次に、すべての要素がその最小値で割り切れるかどうかを確認します。
3. すべて割り切れれば、その最小値を返します。1つでも割り切れない要素があれば、-1 を返します(条件を満たす要素は存在しないことを意味します)。

ここで重要なのは、ある数 x が配列内のすべての要素を割り切るなら、x は必ず配列の最小値でなければならないという点です。したがって、候補として調べるべきは最小値のみで、全要素を総当たりする必要はありません。

C++での実装例

#include<iostream>
#include<algorithm>
using namespace std;

int getNumber(int a[], int n) {
    // 配列内の最小値を取得
    int minNumber = *min_element(a, a + n);

    // すべての要素が最小値で割り切れるかチェック
    for (int i = 0; i < n; i++)
        if (a[i] % minNumber != 0)
            return -1;

    return minNumber;
}

int main() {
    int a[] = { 15, 21, 69, 33, 3, 72, 81 };
    int n = sizeof(a) / sizeof(int);
    cout << "The number is: " << getNumber(a, n);
}

上記のコードでは、min_element() 関数を使って配列の最小値を取得し、その後すべての要素に対して剰余演算(%)を行い、割り切れない要素が1つでもあれば即座に -1 を返すようにしています。最小値自身は必ず自分で割り切れるため、ループは先頭の要素から安全に開始できます。

実行結果

The number is: 3

配列内のすべての要素(15, 21, 69, 33, 72, 81)は3で割り切れるため、正しく 3 が出力されています。

計算量について

このアルゴリズムの計算量は O(n) です。最小値の探索に1回、割り切れるかどうかの判定に1回の走査を行うだけでよいため、配列のサイズに比例した線形時間で処理でき、非常に効率的です。